#include <bits/stdc++.h> using namespace std; typedef array<int, 2> pr; typedef array<int, 3> tp; const int MAX = 200001; int N, A[MAX]; unordered_map<int, tp> dp[MAX]; queue<tp> q; vector<pr> calc(int node, tp X) { vector<pr> res, lv, rv; if ((node << 1) <= N) lv = calc(node << 1, dp[node << 1][X[1]]); if ((node << 1 | 1) <= N) rv = calc(node << 1 | 1, dp[node << 1 | 1][X[2]]); res.resize(lv.size() + rv.size()); merge(lv.begin(), lv.end(), rv.begin(), rv.end(), res.begin()); res.insert(res.begin(), {node, X[0]}); return res; } bool comp(int node, tp X, tp Y) { tp K; if (X[0] ^ Y[0]) return X[0] < Y[0]; else { q.push({node << 1, X[1], Y[1]}), q.push({node << 1 | 1, X[2], Y[2]}); while (!q.empty()) { K = q.front(), q.pop(); if (dp[K[0]][K[1]][0] ^ dp[K[0]][K[2]][0]) { while (!q.empty()) q.pop(); return dp[K[0]][K[1]][0] < dp[K[0]][K[2]][0]; } if ((K[0] << 1) <= N) q.push({K[0] << 1, dp[K[0]][K[1]][1], dp[K[0]][K[2]][1]}); if ((K[0] << 1 | 1) <= N) q.push({K[0] << 1 | 1, dp[K[0]][K[1]][2], dp[K[0]][K[2]][2]}); } } return false; } tp dfs(int node, int val) { if (dp[node].find(val) != dp[node].end()) return dp[node][val]; int X = node << 1, Y = node << 1 | 1; tp res, lv, rv, XV, YV; res = {0, 0, 0}; if (X > N) res[0] = val; else if (Y > N) { if (A[X] > val) res[0] = val, res[1] = A[X], dfs(X, A[X]); else res[0] = A[X], res[1] = val, dfs(X, val); } else { if (val < A[X] && val < A[Y]) { res[0] = val, res[1] = A[X], res[2] = A[Y]; dfs(X, A[X]), dfs(Y, A[Y]); } else if (A[X] < val && A[X] < A[Y]) { res[0] = A[X], res[1] = val, res[2] = A[Y]; dfs(X, val), dfs(Y, A[Y]); } else { lv[0] = A[Y], lv[1] = val, lv[2] = A[X], dfs(X, val), dfs(Y, A[X]); rv[0] = A[Y], rv[1] = A[X], rv[2] = val, dfs(X, A[X]), dfs(Y, val); res = comp(node, lv, rv) ? lv : rv; } } return dp[node][val] = res; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0); int X, Y; vector<pr> ans; cin >> N; for (int i = 1 ; i <= N ; i ++) cin >> A[i]; ans = calc(1, dfs(1, A[1])); for (int i = 1 ; i <= N ; i ++) cout << ans[i - 1][1] << ' '; cout << '\n'; return 0; }