题解

#include<bits/stdc++.h>
using namespace std;
int n=1, a[1000000], dp[1000000], b[2000000],c[2000000];
int main(){
while(cin>>a[n++]){

}
n-=2;

// cout<<n<<endl;
for(int i=1;i<=n;i++){
c[i]=a[n-i+1];
}
int b1=0;
for(int i=1;i<=n;i++){
int x=upper_bound(b+1,b+1+b1,c[i])-b;
if(x>=1&&x<=b1){
b[x]=c[i];
}
else{
b1++;
b[b1]=c[i];
}
}
cout<<b1<<endl;
b1=0;
for(int i=1;i<=n;i++){
int x=lower_bound(b+1,b+1+b1,a[i])-b;
if(x>=1&&x<=b1){
b[x]=a[i];
}
else{
b1++;
b[b1]=a[i];
}
}
cout<<b1;
return 0;
}