#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];

void quick_sort(int st,int dr){

    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]){
            swap(v[i],v[j]);

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

        i+=di;
        j+=dj;
    }


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

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


int main(){

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

    quick_sort(1,n);

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

    return 0;
}