#include <iostream>
#include <vector>
#include <algorithm>

using iter = std::vector<int>::iterator;

int middle(int a, int b, int c) {
    if (b >= a && a >= c || c >= a && a >= b) {
        return a;
    }
    if (a >= b && b >= c || c >= b && b >= a) {
        return b;
    }
    if (a >= c && c >= b || b >= c && c >= a) {
        return c;
    }
}

iter partition2(iter begin, iter end, double predicut) {
    while (begin != end) {
        while (predicut  >=  *begin) {
            ++begin;
            if (begin == end) {
                return begin;
            }
        }
        do {
            --end;
            if (begin == end) {
                return begin;
            }
        } while (predicut <= *end);
        std::swap(*begin, *end);
        ++begin;
    }
    return begin;
}

void quicksort2(iter begin, iter end) {
    if (begin + 1 != end && begin != end) {
        std::cout << *(begin + (end - begin) / 2) << " " << *(begin) << " " << *(end - 1) << '\n';
        std::cout << middle(*(begin + (end - begin) / 2), *(begin), *(end - 1)) << '\n';
        iter end3 = partition2(begin, end,
            middle(*(begin + (end - begin) / 2), *(begin), *(end - 1)));
        std::cout << *end3 << '\n';
        quicksort2(begin, end3);
        quicksort2(end3, end);
    }
}

int main() {
    int a, b, pr;
    std::vector<int> v;
    std::cin >> a;
    if (a != 0) {
        for (int i = 0; i < a; i++) {
            std::cin >> b;
            v.push_back(b);
        }
        quicksort2(v.begin(), v.end());
        int i = 0;
        for (; i < a - 1; i++) {
            std::cout << v[i] << " ";
        }
        std::cout << v[i];
    }
}