#include <fstream>
#include <iostream>
using namespace std;

ifstream fin ("algsort.in");
ofstream fout ("algsort.out");
int a[500001];

void merge_sort(int stanga, int dreapta) {
    cout << stanga << " " << dreapta << "\n";
    if (stanga >= dreapta) {
        return;
    }

    int mijloc, k, i, j, c[dreapta - stanga + 1];

    mijloc = (stanga + dreapta) / 2;

    merge_sort (stanga, mijloc);
    merge_sort (mijloc + 1, dreapta);

    i = stanga; j = mijloc + 1; k = 0;
    while (i <= mijloc && j <= dreapta) {
        if (a[i] < a[j]) {
            c[k] = a[i++];
        }
        else {
            c[k] = a[j++];
        }
        k++;
    }
    while (i <= mijloc) {
        c[k++] = a[i++];
    }
    while (j <= dreapta) {
        c[k++] = a[j++];
    }

    for (i = stanga; i <= dreapta ; i++) {
        a[i] = c[i - stanga];
    }
 }

 int main () {
    int i, n;
    fin >> n;

    for (i = 0; i < n; i++) {
        fin >> a[i];
    }
    merge_sort(0, n - 1);

    for (i = 0; i < n; i++) {
        fout << a[i] << " ";
    }
    return 0;
 }