第四个样例过不去

#include<bits/stdc++.h>
#define N 100010

using namespace std;

int read()
{
    int x = 0,f = 1;
    char c = getchar();
    while(c<'0' || c>'9')
	{
        if(c=='-') f = -1;
        c = getchar();
    }
    while(c>='0' && c<='9')
	{
        x = (x<<3)+(x<<1)+(c^48);
        c = getchar();
    }
    return x*f;
}

int a[N],dp[N];

int main()
{
	int n=read();
	for (int i=1;i<=n;i++)
		a[i]=read();
	dp[1] = a[1];
	int len=1;
	for (int i=2;i<=n;i++)
	{
		if (a[i]>dp[len]) dp[++len] = a[i];
		else dp[(lower_bound(dp+1,dp+n+1,a[i])-dp)] = a[i];
	}
	cout << len << endl;
	return 0; 
}