二分的做法，证明暂时不会。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#include <numeric>

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define for1(i, n) for (int i = 1; i <= int(n); i++)
#define fi first
#define se second
#define pb push_back
#define pob pop_back

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<string,int> PSI;
typedef pair<int,string> PIS;
typedef pair<char,int> PCI;
typedef pair<int,char> PIC;
typedef vector<int> VI;
typedef vector<int,int> VII;
typedef unordered_map<int,int> UII;
typedef set<int> SI;
typedef vector<string> VS;
typedef vector<PII> VPII;

const int INF = 0x3f3f3f3f,MOD = 1e9 + 7;
const int N = 100010,M = N * 2;
const double PI = 3.1415926;

int n,m;
int f[N];
int g[N];

void solve(){
    cin >> n;
    for(int i = 0;i < n;i++)cin >> f[i];
    g[0] = -2e9;
    int idx = 0;
    for(int i = 0;i < n;i++){
        int l = 0,r = idx;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(g[mid] < f[i]) l = mid;
            else r = mid - 1;
        }
        g[r + 1] = f[i];
        idx = max(idx,r + 1);
    }
    cout << idx << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int T = 1;//cin >> T;
    while(T--)solve();
    return 0;
}