#include <bits/stdc++.h>
using namespace std;

class Task { 
 public:
    void solve() {
        read_input();
        get_result();
        print_output();
    }

 private:
    int n;
    vector<int> v;

    void read_input() {
        ifstream fin("algsort.in");
        fin >> n;
        
        v.resize(n);

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

        fin.close();
    }

    int median_of_three(int a, int b, int c) {
        if ((v[a] < v[b]) != (v[a] < v[c])) {
            return a;
        }
        
        if ((v[b] < v[a]) != (v[b] < v[c])) {
            return b;
        }
        
         return c;
    }

    int partition(int start, int end) {
        int mid = start + (end - start) / 2;
        int pivot_index = median_of_three(start, mid, end);
        swap(v[pivot_index], v[end]);
        int pivot = v[end];
        int i = start - 1;
        
        for (int j = start; j < end; j++) {
            if (v[j] <= pivot) {
                i++;
                swap(v[i], v[j]);
            }
        }

        swap(v[i + 1], v[end]);

        return i + 1;
    }

    void quickSort(int start, int end) {
        if (start >= end)
            return;

        int p = partition(start, end);

        quickSort(start, p - 1);
        quickSort(p + 1, end);
    }

    void get_result() {
        quickSort(0, n - 1);
    }

    void print_output() {
        ofstream fout("algsort.out");
        
        for (int i = 0; i < n; i++) {
            fout << v[i] << " ";
        }
        
        fout.close();
    }
};

int main(void) {
    ios::sync_with_stdio(false);
    Task task;
    task.solve();
    return 0;
}