// n是1e5哪得用nlogn的做法，logn需要我们万二分想
// 但是这题这个做法很难想到，但是我们想一下，贪心的可能
// 就是假设lis的长度一样我们让lis最后一个数尽可能小
// 那就要想办法在原有的lis中更新数字使得里面数字尽可能小但仍然满足递增的性质
// 这个办法就是用lower_bound找出第一个大于等于当前的数去替换lis里的那个数，但是
// 如果当前的数大于lis的最后一个数直接添加到末尾即可，才使得lis长度变长
// 然后给出我的例子可以去看理解理解
// 7
// 1 2 4 5 3 4 5
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int a[N],lis[N];

int main()
{
    int len = 0;//开始lis长度是0
    int n; lis[0] = -(1e9 + 1);//比最小的还小才可以把第一个加进去
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
        if(a[i] > lis[len]) lis[++len] = a[i];
        else{
            int pos = lower_bound(lis,lis + len,a[i]) - lis;
            lis[pos] = a[i];
        }
    }
    cout << len << endl;
    return 0;
}