#include<cstdio>
#include<algorithm>
using namespace std;

int a[500005],n;
int pozitie(int p, int u)
{

    int sp=0,su=1;
    while(p<u)
        if(a[p]<=a[u])
            p=p+sp,u=u-su;
        else {
            swap(a[p],a[u]);
            sp=1-sp;su=1-su;
        }
    return p;
}
void quick(int p, int u)
{
    if(p<u){
        int poz=pozitie(p,u);
        quick(p,poz-1);
        quick(poz+1,u);
    }
}
int main()
{
    freopen("algsort.in","r",stdin);
    freopen("algsort.out","w",stdout);
   scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    quick(1,n);
    for(int i=1;i<=n;i++) printf("%d ", a[i]);
    return 0;
}