#include<bits/stdc++.h>
using namespace std;
const long long MaxN = 1e6 +5, INF = 1e18;
long long n, a[MaxN], dp[MaxN];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (long long i=1; i<=n; i++)
    {
        cin >> a[i];
    }
    for (long long i=1; i<=n; i++)
    {
        dp[i]=INF;
    }
    for (long long i=1; i<=n; i++)
    {
        long long pos= lower_bound(dp+1,dp+n+1,a[i])-dp;
        dp[pos]=a[i];
    }
    for (long long i=n; i>=1; i--)
    {
        if(dp[i]<INF)
        {
            cout << i;
            return 0;
        }
    }
}