#include <bits/stdc++.h>

using namespace std;
typedef int var;

ifstream fin("algsort.in");
ofstream fout("algsort.out");

#define MAXN 500005

var ST[MAXN], EN[MAXN], V[MAXN];
var v;
var n;

auto cmp = [](var a, var b) {
    return V[ST[a]] > V[ST[b]];
};
priority_queue<var, vector<var>, decltype(cmp)> pq(cmp);

int main() {
    var n;
    fin>>n;

    for(var i=1; i<=n; i++) {
        fin>>V[i];
    }

    for(var i=1; i<=n;) {

        ST[++v] = i++;
        while(i<=n && V[i] >= V[i-1]) i++;
        EN[v] = i;

        if(i>n) break;

        ST[++v] = i++;
        while(i<=n && V[i] <= V[i-1]) i++;
        EN[v] = i;
        reverse(V+ST[v], V+EN[v]);
    }

    n = 0;
    for(var i=1; i<=v; i++)
        pq.push(i);
    while(!pq.empty()) {
        var i = pq.top();
        pq.pop();

        fout << V[ST[i]] << " ";

        if(++ST[i] < EN[i])
            pq.push(i);
    }
}