//nu face nimic, e o porcarie, iar daca face, devine deja de complexitate prea mare
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main()
{
    int n,i,x,j,m;
    j = 0;
    x = 0;
    FILE *f;
    f = fopen("algsort.in","r");
    fscanf(f,"%d",&n);
    int v[n],k[n];
    k[j] = 1;
    k[j] = k[j] << 30;
    for (i=0;i<n;i++) {
        fscanf(f,"%d",&v[i]);
        if (v[i] < k[j]) k[j] = v[i];
        x++;
        if (x == sqrt(n)) {
            x = 0;
            j++;
            k[j] = 1;
            k[j] = k[j] << 30;
        }
    }
    fclose(f);
    f = fopen("algsort.out","w");
    x = 0;
    while (x < n) {
        m = 0;
        for (j=1;j<sqrt(n);j++)
            if (k[j] < k[m]) m = j;
        for (j=sqrt(n)*m;j<sqrt(n)*(m+1);j++)
            if (v[j] == k[m]) {
                fprintf(f,"%d ",v[j]);
                v[j] = 1;
                v[j] = (v[j] << 30);
                k[m] = v[j];
                break;
            }
        for (j=sqrt(n)*m;j<sqrt(n)*(m+1);j++)
            if (v[j] < k[m]) k[m] = v[j];
        x++;
    }
    fclose(f);
    return 0;
}