#include <iostream>
#include <queue>
#include <vector>
using namespace std;
void printLevelOrder(vector<int> &arr, int n) {
  for (int i = 0; i < n; i++) {
    cout << arr[i] << ' ';
  }
  cout << '\n';
}

int main() {
  int n;
  while (cin >> n) {
    vector<int> a(n);
    vector<int> b(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      b[i] = a[i];
    }

    // Build min heap
    for (int i = 1; i < n; i++) {
      int current = i;
      while (current > 0 && a[current] < a[(current - 1) / 2]) {
        swap(a[current], a[(current - 1) / 2]);
        current = (current - 1) / 2;
      }
    }
    printLevelOrder(a, n);

    // Build max heap
    for (int i = 1; i < n; i++) {
      int current = i;
      while (current > 0 && b[current] > b[(current - 1) / 2]) {
        swap(b[current], b[(current - 1) / 2]);
        current = (current - 1) / 2;
      }
    }
    printLevelOrder(b, n);
  }

  return 0;
}