#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);cin.tie(0);
int n; cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
for (int i = 1; i+1 < n; i += 2) {
int j = (i+1)/2 - 1;
vector<int> vals(3);
vals[0] = a[j];
vals[1] = a[i];
vals[2] = a[i+1];
sort(vals.begin(), vals.end());
int nxti = (i+1)*2-1;
if (nxti+1 < n) {
if (a[nxti] < vals[1] || a[nxti+1] < vals[1])
swap(vals[1],vals[2]);
} else if (nxti < n) {
if (a[nxti] < vals[1] || a[nxti+1] < vals[1])
swap(vals[1],vals[2]);
}
/*
for (int x : a) cerr << x << ' ';
cerr << '\n';
cerr << j << ' ' << i << ' ' << i+1 << '\n'; // */
a[j] = vals[0];
a[i] = vals[1];
a[i+1] = vals[2];
}
if (n%2 == 0) {
int i = n-1;
int j = (i+1)/2 - 1;
if (a[i] < a[j]) swap(a[i], a[j]);
}
for (int x : a) cout << x << ' ';
cout << '\n';
}
