#include <iostream>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;

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

const int N = 1e3 + 2;

int main(){
    int n, v[N], poz[N], um, cnt = 0;
    pair <int,int> mut[N];
    fin >> n;
    um = n + 1;
    v[n + 1] = 0;
    poz[n + 1] = n + 1;
    for(int i = 1; i <= n; i++){
        fin >> v[i];
        poz[v[i]] = i;
    }
    for(int i = 1; i <= n + 1; i++)
        cout << v[i] << ' ';
    cout << '\n';
    for(int i = 1; i <= n + 1; i++)
        cout << poz[i] << ' ';
    for(int i = 1; i <= n; i++){
        fout << i;
        if(v[i] != i){
            if(i != um){
                cnt++;
                mut[cnt].first = i;
                mut[cnt].second = um;
                swap(poz[i], poz[um]);
                um = i;
                fout << '\n' << '*' << '\n';
                for(int i = 1; i <= n + 1; i++)
                    fout << poz[i] << ' ';
                fout << '\n' << um << '\n' << '\n';
                //fout << mut[i].first << ' ' << mut[i].second << '*' << '\n';
            } 
            cnt++;
            mut[cnt].first = poz[i];
            mut[cnt].second = um;
            swap(poz[i], poz[um]);
            um = poz[um];
            for(int i = 1; i <= n + 1; i++)
                fout << poz[i] << ' ';
            fout << '\n' << um << '\n' << '\n';
            //fout << mut[i].first << ' ' << mut[i].second << '\n';
        }
    }
    //fout << cnt << '\n';
    //for(int i = 1; i <= cnt; i++)
    //    fout << mut[cnt].first << ' ' << mut[cnt].second << '\n';
    return 0; 
}