//O(nlogn)
// 
#include <string>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
#include <queue>
using namespace std;
using ll=long long;

//F[i] save the last element min it can obtain of increasing subsequence its length = i 
//dung bs
//lowerbound phan tu dau tien >=a[i]
//in: 9
//1 4 2 3 8 10 6 9 13
//out:6
//ket qua:1 2 3 6 9 13








int main()
{ 
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int n;cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];

    vector<int> res;
    res.push_back(a[0]);
    for(int i=1;i<n;i++)
    {
        auto it =lower_bound(res.begin(),res.end(),a[i]);
        if(it==res.end())
            res.push_back(a[i]);
        else
            *it=a[i];
        // for(int x:res)
        //     cout<<x<<' ';
        // cout<<endl;
    }
    //cout<<endl;
    cout<<res.size();
}