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

int getMin(int left, int right, int a[], int N);
int getMin(int left, int right, int a[], int N, int &pos);

#define max ((1 << 31) - 1)

int main()
{
    int N, i;
    ifstream f("algsort.in");
    f >> N;
    int a[N];
    int pieceSize = sqrt(N);
    int pieceNr;

    if (N % pieceSize == 0)
        pieceNr = N / pieceSize;
    else
        pieceNr = N / pieceSize + 1;

    for (i = 0; i < N; i++)
        f >> a[i];
    f.close();

    int v[pieceNr];
    for (i = 0; i < pieceNr; i++)
        v[i] = getMin(i * pieceSize, (i + 1) * pieceSize - 1, a, N);


    int k = N, min, pos;

    ofstream g("algsort.out");
    while (k)
    {
        min = getMin(0, pieceNr - 1, v, pieceNr, pos);
        for (i = pos * pieceSize; i < (pos + 1) * pieceSize; i++)
            if (a[i] == min)
            {
                g << a[i] << " ";
                a[i] = -1;
                k--;
            }
        v[pos] = getMin(pos * pieceSize, (pos + 1) * pieceSize - 1, a, N);
    }
    g.close();

    return 0;
}

int getMin(int left, int right, int a[], int N)
{
    bool found = false;
    int min = max;
    for (int i = left; i <= right && i < N; i++)
        if (a[i] > - 1 && a[i] < min)
         {
            found = true;
            min = a[i];
        }

    if (!found)
        return -1;

    return min;
}

int getMin(int left, int right, int a[], int N, int &pos)
{
    pos = -1;
    int min = max;
    bool found = false;
    for (int i = left; i <= right && i < N; i++)
        if (a[i] > - 1 && a[i] < min)
        {
            found = true;
            min = a[i];
            pos = i;
        }

    if (!found)
        return -1;
    return min;
}