#include <bits/stdc++.h>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n;
  std::cin >> n;
  std::vector<int> A(n);
  for (int i = 0; i < n; i++) {
    std::cin >> A[i];
  }
  std::vector<int> B(n), L(n, -1), R(n, -1);
  B[0] = 0;
  for (int i = 1; i < n; i++) {
    int root = 0;
    for (;;) {
      if (A[i] < A[root]) {
        if (L[root] == -1) {
          L[root] = i;
          B[i] = B[root] + 1;
          break;
        } else {
          root = L[root];
        }
      } else {
        if (R[root] == -1) {
          R[root] = i;
          B[i] = B[root] + 1;
          break;
        } else {
          root = R[root];
        }
      }
    }
  }
  std::vector<int> C(n, 0);
  auto dfs = [&](auto self, int v) -> void {
    if (L[v] != -1) {
      self(self, L[v]);
      C[v] += C[L[v]] + 1;
    }
    if (R[v] != -1) {
      self(self, R[v]);
      C[v] += C[R[v]] + 1;
    }
  };
  dfs(dfs, 0);
  for (int i = 0; i < n; i++) {
    std::cout << B[i] << " \n"[i + 1 == n];
  }
  for (int i = 0; i < n; i++) {
    std::cout << C[i] << " \n"[i + 1 == n];
  }
}