#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <fstream>
#include <stdio.h>

#define debug 1

using namespace std;

void quicksort(int v[], int st, int dr) {
    #ifdef debug
    printf("sort de %d, %d\n", st, dr);
    #endif

    int a = /*(st + dr) / 2;*/ rand() % (dr - st) + st;

    #ifdef debug
    printf("pivot = %d\n", a);
    #endif // debug

    int pivot = v[a];
    int i = st, j = dr;

    do {
        while (v[i] <= pivot && i <= dr) {
            ++i;
        }

        while (v[j] > pivot && j >= st) {
            --j;
        }

        #ifdef debug
        printf("swap v[%d] = %d, v[%d] = %d\n", i, v[i], j, v[j]);
        #endif

        int aux = v[i];
        v[i] = v[j];
        v[j] = aux;
        ++i;
        --j;
    } while (i <= j);

    #ifdef debug
    printf("v[%d, %d] cu pivot %d = ", st, dr, pivot);
    for (int i = st; i <= dr; i++)
        printf("%d ", v[i]);
    printf("\n");
    #endif

    if (st < j) {
        quicksort(v, st, j);
    }

    if (i < dr) {
        quicksort(v, i, dr);
    }
}

int main()
{
    ifstream fin("sortare.in");
    ofstream fout("sortare.out");

    srand(time(NULL));

    int v[100], n;

    fin >> n;

    for (int i = 0; i < n; i++) {
        fin >> v[i];
        printf("%d ", v[i]);
    }
    printf("\n");

    quicksort(v, 0, n - 1);

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

    fin.close();
    fout.close();

    return 0;
}