#include <iostream>
#include <fstream>

using namespace std;

ifstream f("scmax.in"); ofstream g("scmax.out");

int n,lp,p[100001],a[100001],poz[100001];
int cautbin(int x) {
    int st,dr,mij, last = lp;
    st=1;
    dr=lp;
    mij=0;
    while(st<=dr) {
        mij=(st+dr)/2;
        if (p[mij]>=x) {
            dr=mij-1;
            last = mij;
        }
        if (p[mij]<x) {
            st=mij+1;
        }
    }
    return last;
}

int main() {
    int nr,j,i,pz;
    f>>n;
    for(i=1;i<=n;++i) {
        f>>a[i];
    }
    lp=0;
    p[0]=0;
    for(i=1;i<=n;++i) {
        pz=cautbin(a[i]);
        cout << pz << " ";
        if (pz==lp&& p[lp]<a[i]) {
            ++lp;
            p[lp]=a[i];
            poz[i]=lp;
        }
        else {
        poz[i]=pz;
        p[pz]=a[i];
        }
    }
    nr=0;
    p[0]=100002;
    for(i=lp;i>=1;--i) {
        for(j=n;j>=1;--j) {
            if (poz[j]==i && j<p[nr]) {
                ++nr;
                p[nr]=j;
                break;
            }
        }
    }
    g<<lp<<'\n';
    for(i=lp;i>=1;--i) {
        g<<a[p[i]]<<' ';
    }
    return 0;
}