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

#define int long long
const int mod = 1e9 + 7;
const int INF = 1e10;
const int N = 1e5 + 1;

int my_sol(vector <int> &v){

    int n = (int) v.size();

    set < int > s;
    s.insert(v.front());

    for (int i = 1; i < n; i++){
        int x = v[i];
        auto put = s.upper_bound(x);
        if (put == s.begin()){
            s.insert(x);
        }

        else {
            put--;
            s.erase(put);
            s.insert(x);
        }
    }

    int ans = (int) s.size();
    return ans;
}

int brute(vector <int> v){
    int ans = 0;
    while (!v.empty()){
        ans++;
        vector <int> t;
        int curr = v.front();
        for (int i = 1; i < v.size(); i++){
            if (v[i] > curr){
                curr = v[i];
            }

            else t.push_back(v[i]);
        }
        v = t;
    }
    return ans;
}


signed main(){

    vector <int> v;
    for (int i = 1; i < 11; i++){
        sort(v.begin() , v.end());
        v.push_back(i);
        do {
            if (brute(v) != my_sol(v)){
                for (auto &x : v){
                    cout << x << ' ';
                }
                cout << endl;
                cout << "My code: " <<  my_sol(v) << endl;
                cout << "Brute force: " << brute(v) << endl;
                assert(brute(v) != my_sol(v));

            }
        } while(next_permutation(v.begin() ,v.end()));
    }

    return 0;
}