// O(nlogn)
#include <bits/stdc++.h>
#include <time.h>
using namespace std;

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

// Folosesc partitionarea Lomuto
int partitie(int arr[], int left, int right){
    int pivot = arr[right];
    cout<<"Pivot: "<<pivot<<endl;
    int i = left;
 
    for (int j = left; j <= right - 1; j++)
        if (arr[j] <= pivot) {
            swap(arr[i], arr[j]);
            i++;
        }
    
    swap(arr[i], arr[right]);
    return i; 
}

int partitiePivotRandom(int arr[], int left, int right){
  srand ( time(NULL) );
  int randomIndex = left + rand() % (right-left+1);
	swap(arr[randomIndex], arr[right]);
	return partitie(arr, left, right);
}

void quick(int arr[], int left, int right)
{
	if (left < right) {
		int p = partitiePivotRandom(arr, left, right);

		quick(arr, left, p - 1);
		quick(arr, p + 1, right);
	}
}



// Driver Code
int main()
{ 
	int n;
  f>>n;

  int v[n];
  for(int i=0; i<n; ++i)
    f>>v[i];
  f.close();

  quick(v,0,n-1);

  for(int i=0; i<n; ++i)
    g<<v[i]<<" ";
  g.close();
	return 0;
}