// fara variabile globale zici ca e insane mode...
#include <stdio.h>

using namespace std;

int min(int a, int b) {
    if (a < b)
        return a;
    return b;
}

void update(int minpoz, int de_schimbat, int min_in_b, int n, int radn, int *a, int *b) {
    int aux = a[minpoz];
    a[minpoz] = a[de_schimbat];
    a[de_schimbat] = aux;
    if (min_in_b >= 0)
        for (int i = min_in_b * radn; i < min((min_in_b + 1) * radn, n); i++)
            if(a[i] < a[b[min_in_b]])
                b[min_in_b] = i;
}

void cauta_min(int start, int n, int radn, int *a, int *b) {
    int min = (1 << 30) ^ ((1 << 30) - 1), minpoz = 0, starto = start, min_in_b = -1;
    while (start % radn != 0 && start < n) {
        if (a[start] <= min) {
            min = a[start];
            minpoz = start;
        }
        start++;
    }
    int startrad = start / radn;
    for (int i = startrad; i < radn; i++)
        if (b[i] >= start)
            if (a[b[i]] < min) {
                min = a[b[i]];
                minpoz = b[i];
                min_in_b = i;
            }
    if (minpoz != starto)
        update(minpoz, starto, min_in_b, n, radn, a, b);
}

int main()
{
    freopen("algsort.in", "r", stdin);
    freopen("algsort.out", "w", stdout);
    int n, numar;
    scanf("%i", &n);
    int a[n + 1], radn = 0;
    a[n] = (1 << 30) ^ ((1 << 30) - 1);
    while (radn * radn < n)
        radn++;
    int lung = n / radn + (n % radn > 0), b[lung];
    for (int i = 0; i < radn; i++)
        b[i] = n;
    for (int i = 0; i < n; i++) {
        scanf("%i", &numar);
        a[i] = numar;
        if (a[b[i / radn]] > a[i])
            b[i / radn] = i;
    }
    for (int i = 0; i < n; i++) {
        cauta_min(i, n, radn, a, b);
        printf("%i ", a[i]);
    }
    return 0;
}