#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#define uint unsigned int
#define ll long long
#define INF (1LL<<32)-3
#define DIM 500000
using namespace std;

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

uint n, m, k, pos = 0, len, dx[1005], dy[1005], mn[1005]; 
uint v[500005],a[500005]; int buc[1005];
char sir[DIM];

void Read(uint &x)
{
	f >> x;
	/*while (!isdigit(sir[pos]))
	 if (++pos == DIM) f.read(sir, DIM),pos=0;
	    	  
	x = 0;
	while (isdigit(sir[pos]))
	{
		x = x * 10 + sir[pos] - 48;
		if (++pos == DIM) f.read(sir, DIM), pos = 0;
	}
	*/
}

void Seq()
{
	int i, beg, end;  uint temp;
	beg = 1;

	while (beg <= n)
	{
		end = beg + len - 1;

		if (end > n) end = n;

		k++;  dx[k] = beg; dy[k] = end;

		temp = INF;
	
		for (i = beg; i <= end; i++)
		{
			
			temp = min(temp, v[i]);
			buc[i] = k;
		}

		mn[k] = temp;

	
		beg += len;
	}
}



int main()
{
	int i, j, x, y, poz; uint temp;
	Read(n); 
	len = (int)sqrt(n);

	for (i = 1; i <= n; i++)
		Read(v[i]);

	Seq();
	
	for (i = 1; i <= n; i++)
	{
		temp = INF; poz = 0;
		for (j = 1; j <= k; j++)
		  if (mn[j]<temp) { temp = mn[j]; poz = j; }
	    
		a[i] = temp;

		for (j = dx[poz]; j <= dy[poz]; j++)
			if (v[j] == temp) { v[j] = INF; break; }

		temp = INF;
		for (j = dx[poz]; j <= dy[poz]; j++)
			temp = min(temp, v[j]);

		mn[poz] = temp;
	 
		for (j = 1; j <= n; j++)
			cout << v[j] << " ";

		cout << "\n";
	}

	for (i = 1; i <= n; i++)
		g << a[i] << " ";

	
	return 0;
}