//Judges with GCC >= 12 only needs Ofast
//#pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
//MLE optimization
//#pragma GCC optimize("conserve-stack")
//Old judges
//#pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
//New judges. Test with assert(__builtin_cpu_supports("avx2"));
//#pragma GCC target("arch=skylake")
//Atcoder
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//write variables and debug
#define bugf cout << "Here" << endl
#define bug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define bugarr(arr,...) cout << #arr; _dbg_arr(arr, __VA_ARGS__)
template<class T, class U>
ostream& operator<<(ostream& output, const pair<T, U> &A){
output << "(" << A.first << ", " << A.second << ")";
return output;
}
template <class T>
ostream& operator<<(ostream& output, const vector<T> &arr){
int n = arr.size();
output << "[";
for(int i = 0; i < n; i++){
output << arr[i];
if(i != n - 1) output << ", ";
}
output << "]";
return output;
}
template<class T>
ostream& operator<<(ostream& output, const set<T> &s){
output << "{";
for(auto it = s.begin(); it != s.end(); it++){
if(it != s.begin()) output << ", ";
output << (*it);
}
output << "}";
return output;
}
template<class T, class U>
ostream& operator<<(ostream& output, const map<T, U> &m){
output << "{";
for(auto it = m.begin(); it != m.end(); it++){
if(it != m.begin()) output << ", ";
output << "(" << it->first << " : " << it->second << ")";
}
output << "}";
return output;
}
template<class TH>
void _dbg(const char *sdbg, TH h){
cout << sdbg << " = " << h << endl;
}
template<class TH, class... TA>
void _dbg(const char *sdbg, TH h, TA... a) {
while(*sdbg != ',')cout << *sdbg++;
cout << " = " << h << "\n";
_dbg(sdbg+1, a...);
}
template<class _Arr, class _Index>
void _dbg_arr(_Arr arr, _Index index){
cout << '[' << index << "] = " << arr[index] << endl;
}
template<class _Arr, class _Index, class... TA>
void _dbg_arr(_Arr &arr, _Index index, TA... args){
cout << '[' << index << ']';
_dbg_arr(arr[index], args...);
}
//open file
#define taskname "" //name input and output file
#ifdef SteGG
void open(){
if(fopen("input.inp", "r")){
freopen("input.inp", "r", stdin);
freopen("output.out", "w", stdout);
}
}
#else
void open(){
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
freopen(taskname".out", "w", stdout);
}
}
#endif
//initialize
#define testcase \
long long test; \
cin >> test; \
for(int tst = 1; tst <= test; tst++)
#define int long long
#define MOD 1000000007
#define FFTMOD (119 << 23 | 1)
#define EPSILON 1e-9
#define setpre(x) fixed << setprecision(x)
#define cd complex<double>
#define all(x) x.begin(), x.end()
const long long INF = 3e18L + 5;
const int inf = 1e9 + 7;
const double infd = 1e60;
const double PI = acos(-1);
const int maxn = 2e5 + 5;
//const int base = ;
int n;
int a[maxn];
int result[maxn];
map<pair<int, int>, int> memo;
//others struct or class
struct Node{
int index, val;
Node *left = nullptr, *right = nullptr;
Node(){}
int get_min(){
int result = val;
if(left){
result = min(result, left->val);
}
if(right){
result = min(result, right->val);
}
return result;
}
~Node(){
delete left;
delete right;
}
};
//others function
void dfs1(Node *cur){
int cur_index = cur->index;
int left_index = cur_index * 2;
int right_index = cur_index * 2 + 1;
if(left_index <= n){
cur->left = new Node();
cur->left->val = a[left_index];
cur->left->index = left_index;
dfs1(cur->left);
}
if(right_index <= n){
cur->right = new Node();
cur->right->val = a[right_index];
cur->right->index = right_index;
dfs1(cur->right);
}
}
int depth(Node *cur, int val){ // max depth a val can come to in a subtree root cur
if(cur->left == nullptr) return cur->index;
if(cur->right == nullptr){
if(val < cur->left->val) return cur->index;
else return depth(cur->left, val);
}
if(val < min(cur->left->val, cur->right->val)) return cur->index;
else if(min(cur->left->val, cur->right->val) == cur->left->val){
return depth(cur->left, val);
}
int d1 = depth(cur->left, min(val, cur->left->val));
int d2 = depth(cur->right, min(val, cur->left->val));
if(d1 < d2){
if(cur->left->val > val) return d1;
}else if(cur->left->val < val) return depth(cur->left, val);
if(cur->left->val > val) return d2;
else return depth(cur->right, val);
}
void solve(Node *cur){
if(cur == nullptr) return;
if(cur->get_min() == cur->val){
solve(cur->left);
solve(cur->right);
}else if(cur->get_min() == cur->left->val){
swap(cur->val, cur->left->val);
solve(cur->left);
solve(cur->right);
}else{
swap(cur->val, cur->right->val);
int d1 = depth(cur->left, min(cur->left->val, cur->right->val));
int d2 = depth(cur->right, min(cur->left->val, cur->right->val));
if(d1 < d2){
if(cur->left->val > cur->right->val) {
swap(cur->left->val, cur->right->val);
}
}else if(cur->left->val < cur->right->val){
swap(cur->left->val, cur->right->val);
}
solve(cur->left);
solve(cur->right);
}
result[cur->index] = cur->val;
}
//others init
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
open();
// process input
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
// build binary tree
// consider a basic subtree with 3 node : root, left, right
// if val of root is min -> dfs to left and right
// else if left is min -> swap val with root and continue to dfs
// else if right is min -> there are 2 cases
// use dp to handle
Node *root = new Node();
root->index = 1;
root->val = a[1];
dfs1(root);
solve(root);
for(int i = 1; i <= n; i++){
cout << result[i];
if(i != n) cout << " ";
else cout << endl;
}
return 0;
}
