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

class aib{
    int n;
    vector<int> buf;
public:
    aib(const int N): n(N), buf(n+1, 0){}
    void update(int poz, const int val){
        for(++poz; poz <= n; poz += poz&-poz)
            buf[poz] = max(buf[poz], val); }
    int query(int poz){
        int r = 0;
        for(++poz; poz; poz -= poz&-poz)
            r = max(r, buf[poz]);
        return r; } };

int main(){
    ifstream f("scmax.in");
    ofstream g("scmax.out");
    int n;
    f >> n;
    vector<int> v(n), d(n, 0), sorted(n);
    for(auto& x : v) f >> x;

    copy(begin(v), end(v), begin(sorted));
    sort(begin(sorted), end(sorted));
    sorted.erase(unique(begin(sorted), end(sorted)), end(sorted));

    for(auto& x : v) x = lower_bound(begin(sorted), end(sorted), x) - begin(sorted);

    aib a(n);
    for(int i = 0; i < n; ++i)
        d[i] = a.query(v[i]-1)+1, a.update(v[i], d[i]);

    auto it = max_element(begin(d), end(d));
    int poz = it - begin(d), len = *it, val = v[poz]+1;
    for(const auto x : d) cout << x << ' ';
    cout << endl;
    for(const auto x : v) cout << x << ' ';
    cout << endl;

    vector<int> rez;
    while(len){
        if(val > v[poz] && d[poz] == len) rez.push_back(v[poz]), --len, val = v[poz];
        --poz; }

    reverse(begin(rez), end(rez));

    g << rez.size() << '\n';
    for(const auto x : rez) g << sorted[x] << ' ';
    return 0; }