#include <bits/stdc++.h>

using namespace std;

void _5_sort(vector <short int> &a, int l, int r) {
    if (a[l] > a[l + 1])
        swap(a[l], a[l + 1]);

    if (a[l + 2] > a[r - 1])
        swap(a[l + 2], a[r - 1]);

    if (a[l] > a[l + 2]) {
        swap(a[l + 2], a[l]);
        swap(a[l + 2], a[l + 1]);
    }
    else {
        swap(a[l + 2], a[l + 1]);
        swap(a[l + 2], a[r - 1]);
    }

    if (a[r] > a[l + 1]) {
        swap(a[r], a[r - 1]);
        if (a[r] < a[l + 2])
            swap(a[r - 1], a[l + 2]);
    }
    else {
        if (a[r] < a[l])
            swap(a[r], a[l]);
        swap(a[r], a[l + 1]);
        swap(a[r], a[l + 2]);
        swap(a[r], a[r - 1]);
    }

    if (a[r] < a[l + 2]) {
        if (a[r] < a[l + 1])
            swap(a[r], a[l + 1]);
        swap(a[r], a[l + 2]);
        swap(a[r], a[r - 1]);
    }
    else if (a[r] < a[r - 1])
        swap(a[r], a[r - 1]);
}

void _4_sort(vector <short int> &a, int l, int r) {
    if (a[l] > a[l + 1])
        swap(a[l], a[l + 1]);
    if (a[r - 1] > a[r])
        swap(a[r - 1], a[r]);
    if (a[r - 1] < a[l])
        swap(a[r - 1], a[l]);
    if (a[l + 1] > a[r])
        swap(a[l + 1], a[r]);
    if (a[l + 1] > a[r - 1])
        swap(a[l + 1], a[r - 1]);
}

void _3_sort(vector <short int> &a, int l, int r) {
    if (a[l] > a[l + 1])
        swap(a[l], a[l + 1]);
    if (a[l + 1] > a[r])
        swap(a[l + 1], a[r]);
    if (a[l] > a[l + 1])
        swap(a[l], a[l + 1]);
}

void _2_sort(vector <short int> &a, int l, int r) {
    if (a[l] > a[r])
        swap(a[l], a[r]);
}

int partition(vector <short int> &a, int l, int r) {
    int v = a[(l + r) / 2];

    int i = l , j = r;
    while (i <= j) {
        while (a[i] < v)
            ++i;
        while (a[j] > v)
            --j;

        if (i >= j)
            break;
        swap(a[i++], a[j--]);
    }
    return j;
}

void my_sort(vector <short int> &a, int l, int r) {
    if (l >= r)
        return;
    else if (abs(l - r) == 4)
        _5_sort(a, l, r);
    else if (abs(l - r) == 3)
        _4_sort(a, l, r);
    else if (abs(l - r) == 2)
        _3_sort(a, l, r);
    else if (abs(l - r) == 1)
        _2_sort(a, l, r);

    int m = partition(a, l, r);
    my_sort(a, l, m);
    my_sort(a, m + 1, r);
}

int main() {
    freopen("33554432short_ints.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int n;
    cin >> n;
    vector <short int> a(n);
    for (auto &i : a)
        cin >> i;

    vector <short int> b = a;

    int start = clock();
    my_sort(a, 0, n - 1);
    cout << clock() - start << '\n';
    start = clock();
    sort(b.begin(), b.end());
    cout << clock() - start << '\n';

    for (auto i : a)
        cout << i << ' ';

    return 0;
}