#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
--a[i];
}
vector<vector<int>> vals(n);
vector<map<int, bool>> seen(n);
function<void(int, int)> Build = [&](int i, int v) {
if (i >= n || seen[i][v]) {
return;
}
seen[i][v] = true;
vals[i].push_back(v);
int L = i * 2 + 1, R = i * 2 + 2;
if (L >= n) {
return;
}
if (R >= n) {
if (v < a[L]) {
Build(L, a[L]);
} else {
Build(L, v);
}
return;
}
if (v <= a[L] && v <= a[R]) {
Build(L, a[L]);
Build(R, a[R]);
} else if (a[L] <= v && a[L] <= a[R]) {
Build(L, v);
Build(R, a[R]);
} else {
Build(L, a[L]);
Build(R, v);
Build(L, v);
Build(R, a[L]);
}
};
Build(0, a[0]);
for (int i = 0; i < n; i++) {
sort(vals[i].begin(), vals[i].end());
vals[i].erase(unique(vals[i].begin(), vals[i].end()), vals[i].end());
}
vector<vector<vector<int>>> dp(n);
vector<map<int, int>> idx(n);
auto Merge = [&](int x, vector<int> va, vector<int> vb) {
vector<int> v(1, x);
int pa = 0, pb = 0;
for (int pw = 1; pa < (int) va.size(); pw *= 2) {
for (int iter = 0; iter < pw; iter++) {
if (pa < (int) va.size()) {
v.push_back(va[pa]);
pa += 1;
} else {
break;
}
}
for (int iter = 0; iter < pw; iter++) {
if (pb < (int) vb.size()) {
v.push_back(vb[pb]);
pb += 1;
} else {
break;
}
}
}
return v;
};
function<vector<int>(int, int)> Solve = [&](int i, int v) {
if (i >= n) {
return vector<int>{};
}
if (!idx[i][v]) {
idx[i][v] = (int) dp[i].size();
dp[i].push_back({});
}
int p = idx[i][v];
if (!dp[i][p].empty()) {
return dp[i][p];
}
int L = i * 2 + 1, R = i * 2 + 2;
if (L >= n) {
return dp[i][p] = {v};
}
if (R >= n) {
if (v < a[L]) {
dp[i][p] = Merge(v, Solve(L, a[L]), {});
} else {
dp[i][p] = Merge(a[L], Solve(L, v), {});
}
return dp[i][p];
}
if (v <= a[L] && v <= a[R]) {
dp[i][p] = Merge(v, Solve(L, a[L]), Solve(R, a[R]));
} else if (a[L] <= v && a[L] <= a[R]) {
dp[i][p] = Merge(a[L], Solve(L, v), Solve(R, a[R]));
} else {
dp[i][p] = min(Merge(a[R], Solve(L, a[L]), Solve(R, v)), Merge(a[R], Solve(L, v), Solve(R, a[L])));
}
return dp[i][p];
};
vector<int> dep(n);
for (int i = 1; i < n; i++) {
dep[i] = dep[(i - 1) / 2] + 1;
}
vector<vector<int>> all(n);
for (int i = 0; i < n; i++) {
all[dep[i]].push_back(i);
}
for (int d = n - 1; d >= 0; d--) {
for (int i : all[d]) {
for (int v : vals[i]) {
Solve(i, v);
}
}
if (d + 1 < n) {
for (int i : all[d + 1]) {
dp[i].clear();
idx[i].clear();
}
}
}
vector<int> res;
for (int i = 0; i < (int) vals[0].size(); i++) {
if (vals[0][i] == a[0]) {
res = dp[0][i];
}
}
for (int i = 0; i < (int) res.size(); i++) {
cout << res[i] + 1 << " ";
}
cout << '\n';
return 0;
}
