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

int n;
vector<int> v, ln, lk;
vector<bool> sz;

int kov(int k, int p) {
	k++;
	while(k <= n && sz[k] || (p >= 1 && k < ln[p-1] && k > lk[p-1])) k++;
	return k;
}

int main() {
	cin >> n;
	v.resize(n+1); 
	ln.resize(n+1); 
	lk.resize(n+1);
	sz.resize(n+1, true);
	for(int i = 1; i <= n; i++) cin >> v[i];

	ln[1] = v[1];
	for(int i = 2; i <= n; i++) ln[i] = max(v[i], ln[i-1]);
	lk[1] = v[1];
	for(int i = 2; i <= n; i++) lk[i] = min(v[i], lk[i-1]);

	int p = n;
	int t = 0;
	while(p <= n && n >= 1 && t < 100) {
		int x = kov(v[p], p);
		if(x > n) {
			sz[v[p]] = false;
			v[p] = 0;
			p--;
		} else {
			sz[v[p]] = false;
			sz[x] = true;
			v[p] = x;
			ln[p] = max(v[p], ln[p-1]);//
			lk[p] = min(v[p], lk[p-1]);//
			p++;
		}

		for(int i = 1; i <= n; i++) cout << v[i] << ' ';
		cout << endl;
		for(int i = 1; i <= n; i++) cout << ln[i] << ' ';
		cout << endl;
		for(int i = 1; i <= n; i++) cout << lk[i] << ' ';
		cout << endl << endl;

		t++;
	}

	//for(int i = 1; i <= n; i++) cout << v[i] << ' ';

	return 0;
}