#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
int n;
int a[200001];
vector<vector<int>> dptable;
map<pii, int> dp;
void cmpmerge(vector<int>& target, vector<int>& a1, vector<int>& b1, vector<int>& a2, vector<int>& b2) {
int whi = 0;
int ai = 0, bi = 0;
for (int i = 1; ; i <<= 1) {
if (ai == a1.size()) break;
int ic = 0;
while (ic < i && ai < a1.size()) {
if (whi == 0 && a1[ai] != a2[ai]) {
if (a1[ai] < a2[ai]) whi = 1;
else whi = 2;
}
if (whi < 2) target.push_back(a1[ai++]);
else target.push_back(a2[ai++]);
ic++;
}
ic = 0;
while (ic < i && bi < b1.size()) {
if (whi == 0 && b1[bi] != b2[bi]) {
if (b1[bi] < b2[bi]) whi = 1;
else whi = 2;
}
if (whi < 2) target.push_back(b1[bi++]);
else target.push_back(b2[bi++]);
ic++;
}
}
}
void merge(vector<int>& target, vector<int>& a, vector<int>& b) {
int ai = 0, bi = 0;
for (int i = 1; ; i <<= 1) {
if (ai == a.size()) break;
int ic = 0;
while (ic < i && ai < a.size()) {
target.push_back(a[ai++]);
ic++;
}
ic = 0;
while (ic < i && bi < b.size()) {
target.push_back(b[bi++]);
ic++;
}
}
}
void dfs(int node, int val) {
if (dp.find({node, val}) != dp.end()) return;
dp[{node, val}] = dptable.size();
dptable.push_back(vector<int>());
int l = node << 1, r = node << 1 | 1;
if (n < l) dptable[dp[{node, val}]] = {val};
else if (n < r) dptable[dp[{node, val}]] = min(vector<int>{val, a[l]}, vector<int>{a[l], val});
else {
if (a[r] <= a[l] && a[r] <= val) {
int mi = a[l], ma = val;
if (ma < mi) swap(mi, ma);
dfs(l, mi);
dfs(l, ma);
dfs(r, mi);
dfs(r, ma);
dptable[dp[{node, val}]].push_back(a[r]);
cmpmerge(dptable[dp[{node, val}]], dptable[dp[{l, mi}]], dptable[dp[{r, ma}]], dptable[dp[{l, ma}]], dptable[dp[{r, mi}]]);
}
else if (a[l] < val) {
dfs(l, val);
dfs(r, a[r]);
dptable[dp[{node, val}]].push_back(a[l]);
merge(dptable[dp[{node, val}]], dptable[dp[{l, val}]], dptable[dp[{r, a[r]}]]);
}
else {
dfs(l, a[l]);
dfs(r, a[r]);
dptable[dp[{node, val}]].push_back(val);
merge(dptable[dp[{node, val}]], dptable[dp[{l, a[l]}]], dptable[dp[{r, a[r]}]]);
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
dfs(1, a[1]);
vector<int> ans = dptable[dp[{1, a[1]}]];
for (int i : ans) cout << i << ' ';
cout << '\n';
}
