// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
#include <fstream>
using namespace std;

int v[500003],n,arr[500003];
void quicksort(int left,int right){
if(left<right){
    int pivot = v[rand() % right-1 + left];
    int r=right;
    int l=left;
    int nr=0;
    cout<< left<<"left" <<right <<"right"<<endl;
    for (int i=1;i<=n;i++)
            cout<< arr[i] <<" " ;
            cout <<" before1"<< endl;
    for(int i = left;i<=right;i++){
        if(pivot<v[i])
            arr[r--]=v[i];
        else if(pivot!=v[i])
            arr[l++]=v[i];
        else 
            nr++;
    }
      for (int i=1;i<=n;i++)
            cout<< arr[i] <<" " ;
            cout <<" before2"<< endl;
    int a = l;
    while(nr){
        arr[a]=pivot;
        a++;
        cout << pivot << endl;
        for (int i=1;i<=n;i++)
            cout<< arr[i] <<" ";
        nr--;
        cout << endl;
    }
    cout << l << "l" <<endl;
    for (int i=left;i<=right;i++)
        v[i]=arr[i];
    quicksort(left,l-1);
    quicksort(l+1,right);
}
    
    

}

int main() {
    ifstream f("algsort.in");
    ofstream o("algsort.out");
int i = 1;
f>> n;
for (i=1;i<=n;i++)
    f>> v[i];

quicksort(1,n);


for (i=1;i<=n;i++)
    o<< v[i] <<" ";
    return 0;
}