LIS

#include<bits/stdc++.h>
using namespace std;

unsigned seed=chrono::steady_clock().now().time_since_epoch().count();
mt19937_64 rng(seed);

struct Treap{
    struct node{
        int key,val,pos,pri,sz;
        int mx,mxPos;
        node *lch,*rch;

        node(int _key,int _val,int _pos){
            key=_key;
            val=_val;
            pos=_pos;
            mx=val;
            mxPos=pos;
            pri=rng();
            lch=rch=nullptr;
        }

        void pull(){
            sz=1;
            mx=val;
            mxPos=pos;

            if(lch){
                sz+=lch->sz;
                if(mx<lch->mx || (mx==lch->mx && lch->key>key)){
                    mx=lch->mx;
                    mxPos=lch->mxPos;
                }
            }

            if(rch){
                sz+=rch->sz;
                if(mx<rch->mx || (mx==rch->mx && rch->key>key)){
                    mx=rch->mx;
                    mxPos=rch->mxPos;
                }
            }
        }
    };

    node *rt=nullptr;

    int fs(node *a){
        return a ? a->sz : 0;
    }

    node *merge(node *a,node *b){
        if(!a || !b) return a ? a : b;

        if(a->pri < b->pri){
            a->rch=merge(a->rch,b);
            a->pull();
            return a;
        }else{
            b->lch=merge(a,b->lch);
            b->pull();
            return b;
        }
    }

    void split(node *T,node *&a,node *&b,int v){
        if(!T){
            a=b=nullptr;
            return;
        }

        if(T->key <= v){
            a=T;
            split(T->rch,a->rch,b,v);
            a->pull();
        }else{
            b=T;
            split(T->lch,a,b->lch,v);
            b->pull();
        }
    }

    void splitSz(node *T,node *&a,node *&b,int p){
        if(!T){
            a=b=nullptr;
            return;
        }

        if(fs(T->lch)<p){
            a=T;
            splitSz(T->rch,a->rch,b,p-fs(T->lch)-1);
            a->pull();
        }else{
            b=T;
            splitSz(T->lch,a,b->lch,p);
            b->pull();
        }
    }

    void insert(int k,int v,int p){
        node *a=new node(k,v,p),*b;
        split(rt,rt,b,k);
        rt=merge(rt,a);
        rt=merge(rt,b);
    }

    int find_max(int v){
        node *a;
        split(rt,rt,a,v-1);
        int ret;
        if(!rt) ret=0;
        else ret=rt->mx;
        rt=merge(rt,a);
        return ret;
    }

    int find_max_pos(int v){
        node *a;
        split(rt,rt,a,v-1);
        int ret;
        if(!rt) ret=0;
        else ret=rt->mxPos;
        rt=merge(rt,a);
        return ret;
    }

    void DeleteTree(node *n){
        if(!n) return;
        DeleteTree(n->lch);
        DeleteTree(n->rch);
        delete(n);
    }

    ~Treap(){
        DeleteTree(rt);
    }
};

int dp[100010],v[100010],pre[100010];

// main solution
int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    int n,mx=0;
    cin>>n;

    Treap tp;

    for(int i=1;i<=n;++i){
        int a;
        cin>>a;
        v[i]=a;
        dp[i]=tp.find_max(a)+1;
        pre[i]=tp.find_max_pos(a);
        tp.insert(a,dp[i],i);
        mx=max(mx,dp[i]);
    }

    int mxPos=find(dp+1,dp+1+n,mx)-dp;

    vector<int> lis;
    while(mxPos>0){
        lis.emplace_back(v[mxPos]);
        mxPos=pre[mxPos];
    }

    reverse(lis.begin(),lis.end());

    for(auto i:lis){
        cout<<i<<" ";
    }
    cout<<"\n";
	
    cout<<mx<<"\n";
}