#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
int n, minv = 1e9 + 1, ind = 1;
cin >> n;
vector<int> v(n + 3);
vector<bool> fl(n + 3);
v[n + 1] = 1e9 + 1;
for(int i = 1; i <= n; i++)
{
cin >> v[i];
}
if(v[1] > min(v[2], v[3]))
{
if(v[2] < v[3])
{
swap(v[1], v[2]);
}
else
{
swap(v[1], v[3]);
fl[3] = 1;
}
}
for(int i = 2; i <= n/2; i++)
{
minv = min({v[i], v[2 * i], v[2 * i + 1]});
if(!(i%2))
{
if(fl[i + 1] && minv > v[i + 1])
{
swap(v[i], v[i + 1]);
}
else if(v[2 * i] == minv)
{
swap(v[i], v[2 * i]);
}
else if(v[2 * i + 1] == minv)
{
swap(v[i], v[2 * i + 1]);
fl[2 * i + 1] = 1;
}
}
else
{
if(v[2 * i] == minv)
{
swap(v[i], v[2 * i]);
}
else if(v[2 * i + 1] == minv)
{
swap(v[i], v[2 * i + 1]);
fl[2 * i + 1] = 1;
}
}
}
for(int i = (n/2) + 1; i <= n; i++)
{
if(!(i%2) && fl[i + 1] && v[i + 1] < v[i])
{
swap(v[i], v[i + 1]);
}
}
for(int i = 1; i <= n; i++) cout << v[i] << " ";
return 0;
}
/*
5
3 4 2 5 1
6
3 4 2 5 1 6
3
2 3 1
*/
