#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif

int main()
{
    int64_t n;
    cin >> n;
    vector<int64_t> as(n);
    for (auto &&a : as)
    {
        cin >> a;
        a--;
    }

    vector<pair<int64_t, int64_t>> lrs(n, {-1, -1});

    for (int64_t i = 1; i < n; i++)
    {
        int64_t look = 0;

        while (true)
        {
            if (as[i] < as[look])
            {
                if (lrs[look].first == -1)
                {
                    lrs[look].first = i;
                    break;
                }
                else
                {
                    look = lrs[look].first;
                    continue;
                }
            }
            else if (as[look] < as[i])
            {
                if (lrs[look].second == -1)
                {
                    lrs[look].second = i;
                    break;
                }
                else
                {
                    look = lrs[look].second;
                    continue;
                }
            }
        }
    }

    vector<int64_t> bs(n), cs(n);

    auto dfs = [&](auto &&f, int64_t cur, int64_t depth = 0) -> int64_t
    {
        bs[cur] = depth;

        if (lrs[cur].first != -1)
        {
            cs[cur] += f(f, lrs[cur].first, depth + 1);
        }

        if (lrs[cur].second != -1)
        {
            cs[cur] += f(f, lrs[cur].second, depth + 1);
        }

        return cs[cur] + 1;
    };

    dfs(dfs, 0);

    for (auto &&b : bs)
    {
        cout << b << ' ';
    }
    cout << endl;
    for (auto &&c : cs)
    {
        cout << c << ' ';
    }
    cout << endl;

    return 0;
}