LIS nlogn soln

//In the Name of Allah Most Gracious, Most Merciful//
/*If you want something you've never had, you have  to do something you never did.*/



//LIS nlogn implementation

#include<bits/stdc++.h>
using namespace std;


#define pb push_back
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define M 100007
#define INF 1e9
#define INFL 1e18
#define PI acos(-1)
#define mp make_pair
#define fast_in_out ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//const int fx[]= {+1,-1,+0,+0};
//const int fy[]= {+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move

vector<int>v;
vector<int>tail(M,0);

int Ceilindex(int l,int r,int key)
{
    while(r-l>1)
    {
        int m=l+(r-l)/2;
        if(v[m]>=key)
        {
            r=m;
        }
        else
        {
            l=m;
        }
    }
    return r;
}
int longestIncreasingSubsequenceLength()
{
    if(v.size()==0)
        return 0;
    int length=1;
    tail[0]=v[0];
    for(int i=0;i<v.size();i++)
    {
        if(v[i]<tail[0])
        {
            tail[0]=v[i];
        }
        else if(v[i]>tail[length-1])
        {
            tail[length++]=v[i];
        }
        else
        {
            tail[Ceilindex(-1,length-1,v[i])]=v[i];
        }
    }
    return length;
}
int main()
{
    fast_in_out;
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        v.pb(x);
    }
    int ans=longestIncreasingSubsequenceLength();
    cout<<ans<<endl;

    return 0;
}