rt

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int tree[1000005],dp1[1000005],dp2[1000005],n,a[1000005],maxi,maxj;
void push_up(int cur){
	tree[cur]=max(tree[cur*2],tree[cur*2+1]);
	return;
}
void build(int cur,int lt,int rt){
	int mid=lt+rt>>1;
	if(lt==rt){
		tree[cur]=1;
		return;
	}
	build(cur*2,lt,mid);
	build(cur*2+1,mid+1,rt);
	push_up(cur);
}
void update(int cur,int lt,int rt,int qx,int val){
	if(lt>qx||rt<qx)
		return;
	if(lt==rt){
		tree[cur]=val;
		return;
	}
	int mid=lt+rt>>1;
	update(cur*2,lt,mid,qx,val);
	update(cur*2+1,mid+1,rt,qx,val);
	push_up(cur);
	return;
}
int query(int cur,int lt,int rt,int qx,int qy){
	if(lt>qy||rt<qx)
		return -1e18;
	if(lt>=qx&&rt<=qy)
		return tree[cur];
	int mid=lt+rt>>1;
	return max(query(cur*2,lt,mid,qx,qy),query(cur*2+1,mid+1,rt,qx,qy));
}
signed main(){
	int x;
	while(cin>>x)
		a[++n]=x,maxi=max(maxi,x);
	for(int i=1; i<=n; i++)
		dp1[i]=dp2[i]=1;
	build(1,1,maxi);
	for(int i=1; i<=n; i++){
		dp1[i]=max(dp1[i],query(1,1,maxi,a[i],maxi)+1);
		maxj=max(maxj,dp1[i]);
		update(1,1,maxi,a[i],dp1[i]);
	}
	cout<<maxj-1<<endl;
	maxj=0;
	build(1,1,maxi);
	for(int i=1; i<=n; i++){
		dp2[i]=query(1,1,maxi,1,a[i]-1)+1;
		maxj=max(maxj,dp2[i]);
		update(1,1,maxi,a[i],dp2[i]);
	}
	cout<<maxj-1;
    return 0;
}