#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int n;
int a[100001];
int d[100001];
int p[100001];
int sol[100001];
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++){
        fin>>a[i];
    }
    int k=1;
    d[k]=a[1];
    p[1]=1;
    for(int i=2;i<=n;i++){
        if(a[i]>d[k]){
            d[++k]=a[i];
            p[i]=k;
        }
        else
        {
            int st=1, dr=k, poz=k+1;
            while(st<=dr){
                int mid=(st+dr)/2;
                if(d[mid]>a[i]){
                    poz=mid;
                    dr=mid-1;
                }
                else
                    st=mid+1;
            }
            d[poz]=a[i];
            p[i]=poz;
        }
    }
    for(int i=1;i<=n;i++){
        fout<<d[i]<<" ";
    }
    fout<<"\n";
    for(int i=1;i<=n;i++){
        fout<<p[i]<<" ";
    }
    fout<<"\n";
    int j=n;
    for(int i=k;i>=1;i--){
        while(p[j]!=i)
            j--;
        sol[i]=j;
    }
    fout<<k<<"\n";
    for(int i=1;i<=k;i++)
        fout<<a[sol[i]]<<" ";
    return 0;
}