#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("subsir2.in");
ofstream fout("subsir2.out");

const int nmax = 5005;
int n, a[nmax], d[nmax], p[nmax], sol[nmax];

int main()
{
    int i, k = 1;
    fin>>n;

    for(i = 1; i <= n; ++i)
        fin>>a[i];

    p[1] = 1;
    d[1] = a[1];

    for(i = 2; i <= n; ++i)
    {
        if(a[i] >= d[k])
        {
            d[++k] = a[i];
            p[i] = k;
        }
        else
        {
            if(a[i] <= d[1])
            {
                d[1] = a[i];
                p[i] = 1;
            }
            else
            {
                int st = 1, dr = k, mij, poz = k + 1;
                while(st <= dr)
                {
                    mij = (st + dr) / 2;
                    if(a[i] < d[mij])
                    {
                        poz = mij;
                        dr = mij - 1;
                    }
                    else
                        st = mij + 1;
                }

                d[poz] = a[i];
                p[i] = poz;
            }
        }
    }

    fout<<k<<'\n';
    int copie_k = k;

    /*for(i = n; i > 0; --i)
    {
        if(p[i] == k)
        {
            sol[k] = i;
            //cout<<a[i]<<' ';
            --k;
        }
        if(!k)
            break;
    }

    for(i = 1; i <= copie_k; ++i)
        fout<<sol[i]<<' ';*/
    return 0;
}