#include<iostream>
#include<set>
#include<vector>
using namespace std;

set<int> my_set;
set<int>::iterator it;
vector <int> out;
int main(){
        int n;
        cin>>n;
        for(int i = 1; i <= n; i++) {
        int x;
        cin>>x;
        it = my_set.find(x);
        if(it!=my_set.end() && *it==x){
                continue;
        }
        my_set.insert(x);
        it = my_set.find(x);
        it++;
        if(it != my_set.end())
                my_set.erase(it);
        else
                out.push_back(*it);
//      for(set<int>::iterator it2=my_set.begin();it2!=my_set.end();it2++){
//              cout<<(*it2)<<'*';
//      }
//      cout<<endl;

        }
        cout<<out.size();
}
~            
