// Quicksort cu pivotare hoare
#include <cstdlib>
#include <ctime>
#include <stdio.h>
#include <utility>

#define MAXN 500001

template <typename T>
void quickSort(T* arr, size_t size){
  auto findPivot = [](T* arr, size_t size) -> int {
    int PiPos = rand()%size;
    std::swap(arr[PiPos], arr[0]);

    T pi = arr[0];
    /*printf("pi: %d\n", pi);*/
    int i = 0;
    int j = size-1;

    while(1){

      while(arr[i]<pi)
        i++;

      while(arr[j]>pi)
        j--;

      if(i>=j){
        return j;
      }
      std::swap(arr[i], arr[j]);
      i++;
      j--;
    }
    return j;
  };

  int pivot = findPivot(arr, size);
  if(pivot!=0){
    quickSort(arr, pivot+1);
  }
  if(size-pivot-1>0)
    quickSort(arr+pivot+1, size-pivot-1);
}

int n;
int v[MAXN+1];

int main(){
  srand(time(NULL));
  FILE *fin, *fout;
  fin = fopen("algsort.in", "r");
  fscanf(fin, "%d", &n);
  for(int i = 0; i<n; i++){
    fscanf(fin, "%d", &v[i]);
  }
  fclose(fin);

  quickSort(v, n);

  fout = fopen("algsort.out", "w");
  for(int i=0; i<n; i++){
    fprintf(fout, "%d ", v[i]);
  }
  fprintf(fout, "\n");
  fclose(fout);
  return 0;
}