#include<iostream>
using namespace std;
int dp[10000];
int a[10000];
int n;
//求长度和求和
int LIS_nn()
{
	int ans = 0;
	for (int i = 1;i <= n;++i)
	{
		dp[i] = 1;//dp[i]=a[i];
		for (int j = 1;j < i;j++)
		{
			if(a[j]<a[i])
				dp[i] = max(dp[j] + 1, dp[i]);//dp[i] = max(dp[j] +a[i], dp[i]);
		}
		ans = max(ans, dp[i]);
	}
}
int LIS_nlgn()
{
	int len = 1;
	dp[1] = a[1];
	for (int i = 2;i <= n;++i)
	{
		if (a[i] > dp[len])
			dp[++len] = a[i];
		else
		{
			int pos = lower_bound(dp, dp + len, a[i]) - dp;
			dp[pos] = a[i];
		}
	}
	return len;
}