#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], dp[200001];
void dfs(int node, int val) {
//cout << "dfs " << node << '\n';
int l = node << 1, r = node << 1 | 1;
//cout << l << ' ' << r << '\n';
if (n < l) dp[node] = node;
else if (n < r) {
if (val < a[l]) dp[node] = node;
else dp[node] = l;
}
else {
if (a[l] >= a[r]) {
if (val < a[r]) dp[node] = node;
else if (val < a[l]) {
dfs(l, val);
dfs(r, val);
dp[node] = min(dp[l], dp[r]);
}
else {
dfs(l, a[l]);
dfs(r, a[l]);
if (a[l] <= a[r]) {
dfs(r, val);
dp[node] = dp[r];
}
else if (a[l] > a[r]) {
dfs(l, val);
dp[node] = dp[l];
}
else assert(false);
}
}
else {
if (val < a[l]) dp[node] = node;
else {
dfs(l, val);
dp[node] = dp[l];
}
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
int l = i << 1, r = i << 1 | 1;
if (r <= n) {
if (a[r] <= a[i] && a[r] <= a[l]) {
dfs(l, min(a[i], a[l]));
dfs(r, min(a[i], a[l]));
//cout << i << " : " << l << " = " << dp[l] << ", " << r << " = " << dp[r] << endl;
swap(a[i], a[r]);
int mi = min(a[l], a[r]), ma = max(a[l], a[r]);
if (dp[l] < dp[r]) {
a[l] = mi;
a[r] = ma;
}
else if (dp[l] > dp[r]) {
a[l] = ma;
a[r] = mi;
}
else assert(false);
}
else if (a[l] < a[i]) swap(a[i], a[l]);
}
else if (l == n) {
if (a[l] < a[i]) swap(a[i], a[l]);
}
cout << a[i] << ' ';
//for (int j = 1; j <= n; j++) cout << a[j] << ' ';
//cout << '\n';
}
cout << '\n';
}
