#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>

using namespace std;

#define rep(i,a,n) for (int i=a;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define PI 3.14159265358979323846

typedef long long ll;
typedef long double ld;

void fastIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

const int mxn = 5e5 + 228;
int n;
int l[mxn];
int r[mxn];
vector<int> a;

void calc_lr() {
    vector<int> st;
    for (int i = 0; i <= n + 1; ++i) {
        while (!st.empty() && a[i] <= a[st.back()]) {
            st.pop_back();
        }
        if (st.empty()) {
            l[i] = -1;
        }
        else {
            l[i] = st.back();
        }
        st.push_back(i);
    }
    st.clear();
    for (int i = n + 1; i >= 0; --i) {
        while (!st.empty() && a[i] < a[st.back()]) {
            st.pop_back();
        }
        if (st.empty()) {
            r[i] = n + 2;
        }
        else {
            r[i] = st.back();
        }
        st.push_back(i);
    }
}


int main() {
    fastIO();
    cin >> n;
    a.resize(n + 3);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    calc_lr();
    for (int i = 0; i < n; ++i) {
        cout << l[i] << " ";
    }
    cout << endl;
    for (int i = 0; i < n; ++i) {
        cout << r[i] << " ";
    }

}