/*
 * @Author: YMYS
 * @Date: 2024-03-25 21:47:58
 * @LastEditTime: 2024-12-21 20:58:26
 * @FilePath: \VScode-C&C++-Coding\Acwing\算法基础课\5.第五章\2.线性DP\3.最长上升子序列2.cpp
 * @URL:https://www.acwing.com/problem/content/898/
 * @Description: 895.最长上升子序列2
 * dp：n^2做法 ; 贪心：nlogn做法
 */
#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+10;

int n;
vector<int> dp;
vector<int> a;//a是一个vector<int>，也就是一个数组，有N个int
// vector<int> a[N];//a是N个vector<int>,相当于二维数组了

int main()
{
#ifdef ABC
    freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
    freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
#endif
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];

    dp.push_back(a[0]);//因为是用值来作为判断条件，所以必须提前在dp数组中存入一个数。
    //如果是用指针来判断，则不用提前存入东西
    for(int i=1;i<n;i++){
        if(a[i] > dp.back()) dp.push_back(a[i]);
        else *lower_bound(dp.begin(), dp.end(), a[i]) = a[i];//lower返回大于or等于，upper返回大于
    }

    cout << dp.size() << endl;

    return 0;
}