#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000010;
ll n,n1,n2,a[N],a1[N],a2[N],c[N],ans1,ans2;
void msort1 (int l,int r) {
    if (l==r) return;
    ll mid=(l+r)/2;
    msort1(l,mid);
	msort1(mid+1,r);
	ll ll=l,rr=mid+1,sum=l;
    while (ll<=mid&&rr<=r) {
    	if (a1[ll]<=a1[rr]) c[sum++]=a1[ll++];
    	else c[sum++]=a1[rr++],ans1+=mid-ll+1;
	}
    while (ll<=mid) c[sum++]=a1[ll++];
    while (rr<=r) c[sum++]=a1[rr++];
    for (int i=l;i<=r;i++) a1[i]=c[i];
} 
void msort2 (int l,int r) {
    if (l==r) return;
    ll mid=(l+r)/2;
    msort2(l,mid);
	msort2(mid+1,r);
	ll ll=l,rr=mid+1,sum=l;
    while (ll<=mid&&rr<=r) {
    	if (a2[ll]<=a2[rr]) c[sum++]=a2[ll++];
    	else c[sum++]=a2[rr++],ans2+=mid-ll+1;
	}
    while (ll<=mid) c[sum++]=a2[ll++];
    while (rr<=r) c[sum++]=a2[rr++];
    for (int i=l;i<=r;i++) a2[i]=c[i];
} 
int main () {
	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0); 
	cin >> n;
	for (int i=1;i<=n;i++) cin >> a[i];
	for (int i=1;i<=n;i++) {
		if (i%2==1) a1[++n1]=a[i];
		else a2[++n2]=a[i];
	}
	msort1(1,n1);
	memset(c,0,sizeof(c));
	msort2(1,n2);
	if (ans1%2==ans2%2) {
		//if (n%2==0) swap(a2[n2],a2[n2-1]);
		//else swap(a1[n1],a1[n1-1]);
		for (int i=1;i<=n;i++) {
			if (i%2==1) cout << a1[i/2+1] <<' ';
			else cout << a2[i/2] <<' ';
		}
	}else{
		if (n%2==0) swap(a2[n2],a2[n2-1]);
		else swap(a1[n1],a1[n1-1]);
		for (int i=1;i<=n;i++) {
			if (i%2==1) cout << a1[i/2+1] <<' ';
			else cout << a2[i/2] <<' ';
		}
	}
	return 0;
}