#include <algorithm>
#include <iostream>
#include <set>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include <set>
#include <string>
#include <fstream>
#include <list>
#include <numeric>
#include <random>
#include <queue>

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);
}

int n;
vector<ll> lsr;
vector<ll> lsl;
vector<ll> a;
vector<ll> dpl;
vector<ll> dpr;


void calc() {
    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()) {
            lsl[i] = -1;
        }
        else {
            lsl[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()) {
            lsr[i] = n + 2;
        }
        else {
            lsr[i] = st.back();
        }
        st.push_back(i);
    }
}


void solve() {
    for (int i = 1; i <= n; ++i) {
        dpl[i] = a[i] * (i - lsl[i]) + dpl[lsl[i]];
    }
    for (int i = n; i >= 1; --i) {
        dpl[i] = a[i] * (lsr[i] - i) + dpr[lsr[i]];
    }
}


int main() {
    fastIO();
    cin >> n;
    a.resize(n + 2);
    lsl.resize(n + 2);
    lsr.resize(n + 2);
    dpl.resize(n + 1);
    dpr.resize(n + 1);
    rep(i, 1, n + 1) {
        cin >> a[i];
    }
    calc();
    rep(i,1,n + 1) {
        cout << dpl[i] << " ";
    }
    cout << endl;
    rep(i, 1, n + 1) {
        cout << lsr[i] << " ";
    }
}