#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int n;cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++){
        int aa;cin>>aa;
        aa--;
        a[i]=aa;
    }
    const int inf=1e18;
    vector<pair<int,int>>to(n,{inf,inf});
    vector<int>b(n,0);
    for(int i=1;i<n;i++){
        int now=a[0];
        int deep=0;
        while(true){
            if(a[i]<now){
                if(to[now].first==inf){
                    to[now].first=a[i];
                    b[i]=deep+1;
                    break;
                }else{
                    now=to[now].first;
                    deep++;
                    continue;
                }
            }else{
                if(to[now].second==inf){
                    to[now].second=a[i];
                    b[i]=deep+1;
                    break;
                }else{
                    now=to[now].second;
                    deep++;
                    continue;
                }
            }
        }
    }
    for(int i=0;i<n;i++)cout<<b[i]<<" ";
    cout<<endl;
    vector<int>c(n,0);
    vector<bool>vis(n);
    vis[a[0]]=true;
    auto dfs=[&](auto dfs,int now)->int{
        int ret=1;
        if(to[now].first!=inf){
            if(!vis[to[now].first]){
                vis[to[now].first]=true;
                ret+=dfs(dfs,to[now].first);
            }
        }
        if(to[now].second!=inf){
            if(!vis[to[now].second]){
                vis[to[now].second]=true;
                ret+=dfs(dfs,to[now].second);
            }
        }
        c[now]=ret;
        return ret;
    };
    dfs(dfs,a[0]);
    for(int i=0;i<n;i++)cout<<c[a[i]]-1<<" ";
    cout<<endl;
    // for(int i=0;i<n;i++){
    //     cout<<"now -> "<<a[i]+1<<endl;;
    //     cout<<"first -> "<<to[a[i]].first+1<<" second -> "<<to[a[i]].second+1<<endl;
    // }
}