#include <bits/stdc++.h> using namespace std; typedef array<int, 2> pr; typedef array<int, 3> tp; const int MAX = 200001; const int MAX_LOG = 40; int N, A[MAX], V[MAX]; map<int, int> B[MAX]; map<pr, pr> _comp[MAX]; // {i, j}가 처음으로 다른 {index, i < j} tp dp[MAX_LOG][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[B[node << 1][X[1]]][node << 1]); if ((node << 1 | 1) <= N) rv = calc(node << 1 | 1, dp[B[node << 1 | 1][X[2]]][node << 1 | 1]); 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; } pr comp(int node, int X, int Y) { int XN = B[node][X], YN = B[node][Y]; bool rev = XN > YN; pr K, LV, RV; if (rev) swap(XN, YN); if (_comp[node].find({XN, YN}) != _comp[node].end()) { K = _comp[node][{XN, YN}]; return {K[0], K[1] ^ rev}; } if (XN == YN) K = {N + 1, 0}; else if (dp[XN][node][0] ^ dp[YN][node][0]) K = {node, dp[XN][node][0] < dp[YN][node][0]}; else { LV = comp(node << 1, dp[XN][node][1], dp[YN][node][1]); if ((node << 1 | 1) > N) K = LV; else if (LV[0] == (node << 1)) K = LV; else { RV = comp(node << 1 | 1, dp[XN][node][2], dp[YN][node][2]); K = LV[0] < RV[0] ? LV : RV; } } _comp[node][{XN, YN}] = K; return {K[0], K[1] ^ rev}; } bool comp(int node, tp X, tp Y) { pr XV, YV; if (X[0] ^ Y[0]) return X[0] < Y[0]; else { XV = comp(node << 1, X[1], Y[1]), YV = comp(node << 1 | 1, X[2], Y[2]); return XV[0] < YV[0] ? XV[1] : YV[1]; } } tp dfs(int node, int val) { if (B[node].find(val) != B[node].end()) return dp[B[node][val]][node]; 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; } } B[node][val] = V[node]; return dp[V[node] ++][node] = 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; }