#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N=2e5+5;
int n,L_cnt,X_cnt,edgenum;
int fa[N],L_ans[N],X_ans[N],L_rank[N],X_rank[N],min_point[N];
int fir[2*N],nex[2*N],en[N];

struct cmp1 {
    bool operator () (int &a,int &b) {
    	return min_point[a]>min_point[b];//最小值优先 
	}
};

struct cmp2 {
    bool operator () (int &a,int &b) {
    	return a<b;//最大值优先 
	}	
};

priority_queue<int,vector<int>,cmp1> L_que; 
priority_queue<int,vector<int>,cmp2> X_que;

inline int input() {
	char ch;
	int sign=1;
	while((ch=getchar())<'0' || ch>'9')
	    if(ch=='-') sign=-1;
	int res=ch-'0';
	while((ch=getchar())>='0' && ch<='9')
	    res=10*res+ch-'0';
	return res*sign;
}

void Build(int u,int v) {
	nex[++edgenum]=fir[u];
	en[edgenum]=v;
	fir[u]=edgenum;
}

void dfs(int x) {
	int i=x;
	for(i=fir[i];i;i=nex[i]) {
		if(en[i]<min_point[x]) min_point[x]=en[i];
		dfs(en[i]);
	}
}

void L_solve(int x) {
	if(L_que.empty()) return ;
	L_ans[++L_cnt]=L_que.top();
	L_rank[L_que.top()]=L_cnt;
	L_que.pop();
    int i=x; 
    for(i=fir[i];i;i=nex[i]) L_que.push(en[i]);
	L_solve(L_que.top());
}

void X_solve(int x) {
	if(X_que.empty()) return ;
	X_ans[++X_cnt]=X_que.top();
	X_rank[X_que.top()]=X_cnt;
	X_que.pop();
    int i=x;
    for(i=fir[i];i;i=nex[i]) X_que.push(en[i]);
	X_solve(X_que.top());
}

int main() {
	n=input();
	for(int i=1;i<=n;i++) {
		fa[i]=input();
        Build(fa[i],i);
        min_point[i]=i;
		if(fa[i]==0) {
			L_que.push(i);
			X_que.push(i);
		}
	}
	for(int i=1;i<=n;i++) dfs(i);
	L_solve(L_que.top());
	X_solve(X_que.top());
    for(int i=1;i<=n;i++) cout<<L_rank[i]<<" ";
    cout<<endl;
    for(int i=1;i<=n;i++) cout<<X_rank[i]<<" ";
	return 0;
}