up

#include <fstream>
using namespace std;
int n,i,v[100001],c[100001],a[100001],t,st,dr,poz,mij,b[10001],k;

int main()
{
    ifstream f("up.in");
    ofstream g("up.out");
    f>>n;
    for(i=1;i<=n;++i)
    {
       f>>v[i];
    }
    a[1]=v[1];
    t=1;
    c[1]=1;
    for(i=2;i<=n;++i)
    {
        ///plasez elementul v[i] in a astfel incat sirul a este crescator
        if(v[i]>a[t]) {a[++t]=v[i];
                        c[i]=t;}
        else {
            ///caut binar pozitia
            st=1;
            dr=t;
            poz=0;
            while (st<=dr)
            {
                mij=(st+dr)/2;
                if(a[mij]>=v[i])
                    poz=mij,dr=mij-1;
                else
                    st=mij+1;
            }
            a[poz]=v[i];
            c[i]=poz;
        }
    }
    g<<t<<'\n';
    return 0;
}