MULTISET_LIS

/* IF DUPLICASY IS ALLOWED*/

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

int main()
{
    int n,g;
    multiset<int> s;
    multiset<int>::iterator it;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>g;
        s.insert(g);
        it = s.upper_bound( g);
        cout<<*it<<endl;
        if(it!=s.end())
        s.erase(it);
    }
    cout<<s.size()<<endl;
    return 0;
}

/* IF DUPLICASY IS NOT ALLOWED THAN RELACE upper_bound by find or use set instead of multiset