#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    const int INF=1e9;
    vector<int> dp(n,INF);
    for(int i=0;i<n;i++){
        int t=lower_bound(dp.begin(),dp.end(),a[i])-dp.begin();
        dp[t]=a[i];
    }
    cout << n-(lower_bound(dp.begin(),dp.end(),INF)-dp.begin()) << endl;
}