#include <iostream>
using namespace std;
struct st{
	int d,link;
} a[10000];
int head,n;
int ins(int i){
	int p;
	if(a[i].d<=a[head].d){
		a[i].link=head;
		head=i;
	}
	else{
		p=head;
		while(a[p].link!=0&&a[a[p].link].d<a[i].d) p=a[p].link;
		a[i].link=a[p].link;
		a[p].link=i;   
	}
   return 0;	
}
void prt(int k){
	int i;
	for(i=1;i<=k;i++) cout<<a[i].d<<" ";
	cout<<endl;
	for(i=1;i<=k;i++) cout<<a[i].link<<" ";
	cout<<endl;	
}
int main(){
	int i,p;
	cin>>n;
    for(i=1;i<=n;i++)  cin>>a[i].d;
	head=1;
	a[head].link=0; 	
	for(i=2;i<=n;i++) ins(i);
	p=head;
	while(p!=0){
		cout<<a[p].d<<" ";		
		p=a[p].link;
	}
     cout<<endl;
     prt(n); 

   return 0; 	
}