当前没有测试数据。

题目背景

知周所众，有四个序列： 注意这里 $a1,a2,ak$ 不要求连续

输入输出

输入有两行。首行一个整数 $N$ ，表示序列长度。第二行 $N$ 个整数，表示这个序列 输出仅一行。用 $printf$ 输出四个用空格分开的整数，按顺序表示这四个序列的长度

说明提示

这里给出DP暴力解法用于理解题意：

cin>>n;
int a[N],dp[N],t[N];
for(int i=1;i<=n;i++){
	cin>>a[i];
	dp[i]=1;
}
for(int i=1;i<=n;i++){
	for(int j=1;j<i;j++)
		if(a[j]<a[i]||a[j]<=a[i]||a[j]>a[i]||a[j]>=a[i])
			dp[i]=max(dp[i],dp[j]+1); 
	ans=max(ans,dp[i]);
}

现在邪恶的出题人要求你们使用 $O(nlogn)$ 的二分优化方法通过此题，因为： $1<=ai<=1e9,1<=N<=1e5$ 。