#include<bits/stdc++.h>
#define ll long long
#define N ((int)6e4 + 5)
#define MOD ((int)1e9 + 7)
#define MAX ((int)1e9 + 7)
#define MAXL ((ll)1e18 + 7)
#define MAXP ((int)1e3 + 7)
#define thr 1e-8
#define pi acos(-1)  /// pi = acos ( -1 )
#define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
#define endl "\n"

using namespace std;


/// LIS
int arr[N] , dpp[N], lastEle[N];

int binarySearch(int arr[] , int val)
{
    int lef = 0 , rig = n;
    while(lef < rig){
        int mid = (lef + rig + 1) >> 1;
        if(arr[mid] < val) lef = mid;
        else rig = mid-1;
    }
    return lef;
}

int main(){
    int n;
    cin>>n;
    for(int i = 1; i <= n ; i++){
        cin>>arr[i];
        lastEle[i] = MAX;
    }
    lastEle[0] = -MAX;
    for(int i = 1 ; i <= n ; i++){
        int len = binarySearch(lastEle , arr[i] , n);
        lastEle[len+1] = min(lastEle[len+1] , arr[i]);
        dpp[i] = len+1;
    }
}