#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
int a[maxn] , dp[maxn] , len = 0;
int read()
{
	int i = 0;
	while(scanf("%d" , &a[++i])!=EOF);
	return i - 1;
}
int main ()
{
	int n = read();
	dp[0]=2147483647;
	for (int i = 1; i <= n; i++)
	{
		if (a[i] <= dp[len])dp[++len]=a[i];
		else 
		{
			int p = upper_bound(dp + 1 , dp + len + 1 , a[i] , greater<int>()) - dp;
			dp[p]=a[i];
		}
	}
	printf("%d\n" , len);
	len = 0;
	memset(dp , 0 , sizeof(dp));
	dp[0]=0;
	for (int i = 1; i <= n; i++)
	{
		if (a[i] > dp[len])dp[++len]=a[i];
		else 
		{
			int p = lower_bound(dp + 1 , dp + len + 1 , a[i]) - dp;
			dp[p]=a[i];
		}
	}
	printf("%d" , len);
	return 0;
}

代码洛谷上能过，但是学校的OJ上50ptsWA，复制洛谷的题解也都是错一样的点