/*

首先想想从逻辑上这个题应该怎么做
假设最后我们会得到很多序列，最长的那个序列就是我们想要的序列，他的长度就是我们想要的长度
那么假设我们正处在其中的一步我们接下来应该怎么做才能慢慢达到我们的目的？
加入我们此时已经知道有几个序列了每个序列的最后一个元素的大小
并且我们要求同一长度的序列的最后一个值是他可以取到的最小值
可以通过反证法轻易证出当前的序列的最后一个值的大小从有序的，是从小到大排序的

*/

#include<iostream>

using namespace std;

int a[100000+10];
int len,n;
int last[100000+10];

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];

    last[0]=-0x3f3f3f3f;
    for(int i=0;i<n;i++)
    {
        //注意这里有一个经验就是遇到找数就要考虑能不能二分
        int l=0,r=len;
        while(l<r)
        {
            int mid = l+r+1>>1;
            if(last[mid]<a[i])l=mid;
            else r = mid-1;
        }
        len=max(len,l+1);
        last[l+1]=a[i];
    }
    cout<<len;
    return 0;
}