#include<fstream>
#include<cmath>
using namespace std;
ifstream cin("algsort.in");
ofstream cout("algsort.out");
int n,v[500005],b[805],rad;
int q(int s,int d){
    int rez=s;
    if(s/rad==d/rad){
        for(int i=s;i<=d;i++)
            if(v[i]<v[rez]) rez=i;
        return rez;
    }
    int bs=s/rad,bd=d/rad;
    for(int i=s;i<=(bs+1)*rad-1;i++)
        if(v[i]<v[rez]) rez=i;

    for(int i=bs+1;i<=bd-1;i++)
        if(v[b[i]]<v[rez]) rez=b[i];

    for(int i=bd*rad;i<=d;i++)
        if(v[i]<v[rez]) rez=i;

    return rez;
}
void u(int p1,int p2){
    int b1=p1/rad,b2=p2/rad;
    int a=v[p1],c=v[p2];
    v[p1]=v[p2]=~(1<<31);
    for(int i=b1*rad;i<(b1+1)*rad;i++)
        if(v[i]<v[b[b1]]) b[b1]=i;
    for(int i=b2*rad;i<(b2+1)*rad;i++)
        if(v[i]<v[b[b2]]) b[b2]=i;
    v[p1]=c; v[p2]=a;
    if(v[p1]<v[b[b1]]) b[b1]=p1;
    if(v[p2]<v[b[b2]]) b[b2]=p2;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>v[i];
    rad=sqrt(n)+1;

    for(int i=0;i<n;i++)
        if(i%rad==0) b[i/rad]=i;
        else if(v[i]<v[b[i/rad]]) b[i/rad]=i;

    for(int i=0;i<n-1;i++){
        int p=q(i,n-1);
        u(i,p);
    }
    for(int i=0;i<n;i++)
        cout<<v[i]<<' ';
}