#include <fstream>
using namespace std;
ifstream in ("adlic.in");
ofstream out ("adlic.out");
int main ()
{
    int cerinta;
    in>>cerinta;
    if (cerinta==1)
    {
        int n,ok=0,k;
        in>>n;
        in>>k;
        for (int i=1;i<=n-1;++i)
        {
            int a;
            in>>a;
            if (a<=k)
            {
                out<<a;
                return 0;
            }
        }
    }
    else
    {
        int cnt=1,k,n,v[1000001];
        in>>n;
        for (int i=1;i<=n;++i)
        {
            in>>k;
            int l=1,r=cnt,best;
            while (l<=r)
            {
                int mid=(l+r)/2;
                if (v[mid]<=k)
                {
                    best=mid;
                    r=mid-1;
                }
                else
                    l=mid+1;
            }
            if (v[best]==0)
                cnt++;
            v[best]=k;
        }
        out<<cnt-1;
        return 0;
    }

}