#include <bits/stdc++.h>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N), L(N, -1), R(N, -1), P(N, -1);
    cin >> A[0];
    A[0]--;
    auto insert = [&] (auto insert, int p, int i) {
        if (p < i) {
            if (R[p] == -1) {
                R[p] = i;
                P[i] = p;
                return;
            }
            insert(insert, R[p], i);
        } else {
            if (L[p] == -1) {
                L[p] = i;
                P[i] = p;
                return;
            }
            insert(insert, L[p], i);
        }
    };
    for (int i = 1; i < N; i++) {
        cin >> A[i];
        A[i]--;
        insert(insert, A[0], A[i]);
    }

    vector<int> B(N, -1), C(N, -1);
    auto solve = [&] (auto solve, int a, int depth) -> int {
        int ans = 0;
        if (R[a] != -1) {
            ans += solve(solve, R[a], depth + 1);
        }
        if (L[a] != -1) {
            ans += solve(solve, L[a], depth + 1);
        }
        B[a] = depth;
        C[a] = ans;
        return ans + 1;
    };
    solve(solve, A[0], 0);
    for (int i: A) cout << B[i] << ' ';
    cout << endl;
    for (int i: A) cout << C[i] << ' ';
    cout << endl;
    return 0;
}