RT
思路是分别求不上升子序列（倒序求不下降子序列） 和上升子序列
代码如下
为什么前者结果需要减一，后者却不需要 QAQ

#include<iostream>
#include<algorithm>
using namespace std;
int dd[100010],you[100010],zuo[100010];
int n,m,ny,nz;
int main(){
	while(scanf("%d",&dd[++n])!=EOF);
	for(int i=n;i>=1;i--){
		if(dd[i]>=you[ny]) you[++ny]=dd[i];
		else *upper_bound(you+1,you+1+ny,dd[i])=dd[i];
	}
	for(int i=1;i<=n;i++){
		if(dd[i]>zuo[nz]) zuo[++nz]=dd[i];
		else *lower_bound(zuo+1,zuo+1+nz,dd[i])=dd[i];
	}
	cout<<ny-1<<endl<<nz;
}