#include <bits/stdc++.h>

#define DIM 500000

using namespace std;

ifstream f("algsort.in");
ofstream g("algsort.out");

//ifstream f("filesmodel.in");
//ofstream g("filesmodel.out");

int n;
int v[DIM+5];
int r[DIM+5];

void quick_sort(int st,int dr,int cond){

    //cout<<st<<" "<<dr<<'\n';

    if(st >= dr){
        return;
    }

    int i = st;
    int j = dr;
    int di = 0;
    int dj = -1;

    while(i<j){

        if( (v[i] > v[j] && cond == 1) ||
            (r[i] > r[j] && cond == 0)){
            swap(v[i],v[j]);
            swap(r[i],r[j]);

            int aux = di;
            di = -dj;
            dj = -aux;
        }

        i+=di;
        j+=dj;
    }


    if(i == j){
        j--;
        i++;
    }

    quick_sort(st,j,cond);
    quick_sort(i,dr,cond);
}

int main(){

    srand(time(0));

    f>>n;
    for(int i=1;i<=n;i++){
        f>>v[i];
        r[i] = rand();
    }

    quick_sort(1,n,0);

    /*for(int i=1;i<=n;i++){
        cout<<v[i]<<" ";
    }*/

    quick_sort(1,n,1);

    for(int i=1;i<=n;i++){
        g<<v[i]<<" ";
    }

    return 0;
}