用的cdq

#include<bits/stdc++.h>
using namespace std;
int n,ans1,ans2;
struct node{
	int id,h,dp1,dp2;
	//dp1最长不上升,dp2最长上升 
}a[500005];
bool cmp1(node x,node y){ //按h排序 
	return x.h<y.h;
}
bool cmp2(node x,node y){ //按id排序 
	return x.id<y.id;
}
void CDQ(int l,int r){
	if(l == r)return;
	int mid = (l+r)/2;
	CDQ(l, mid);
	sort(a+l, a+mid+1, cmp1);
	sort(a+mid+1, a+r+1, cmp1);
	int j = l,mx = 0;
	for(int i = mid+1; i <= r; i++) {
		while(a[j].h < a[i].h && j <= mid)
			mx = max(mx, a[j++].dp2);
		a[i].dp2 = max(a[i].dp2, mx+1);
	}
	j = mid,mx = 0;
	for(int i = r; i >= mid+1; i--) {
		while(a[j].h >= a[i].h && j >= 1)
			mx = max(mx, a[j--].dp1);
		a[i].dp1 = max(a[i].dp1, mx+1);
	}
	sort(a+mid+1, a+r+1, cmp2);
    CDQ(mid+1, r);
}
int main(){
	n = 1;
	while(cin>>a[n].h) {
		a[n].id = n;
		a[n].dp1 = a[n].dp2 = 1;
		n++;
	}
	n--;
	CDQ(1, n);
	for(int i = 1; i <= n; i++) {
		ans1 = max(ans1,a[i].dp1);
		ans2 = max(ans2,a[i].dp2);
	}
	cout<<ans1<<endl<<ans2;
	return 0;
}