#include <stdio.h>
#include <stdlib.h>

#define ListType int

typedef struct _CC_LIST_ENTRY{
    int Value;
    struct _CC_LIST_ENTRY *Pre, *Urm;
} CC_LIST_ENTRY;

int LstCreate( CC_LIST_ENTRY **List )
{
    /// primul nod din lista va tine minte numarul de elemente din lista
    *List = ( CC_LIST_ENTRY * )malloc( sizeof( CC_LIST_ENTRY ) );
    if( *List == 0 ) return -1;
    (*List) -> Value = 0;
    (*List) -> Pre = (*List) -> Urm = *List;
    return 0;
}

int LstDestroy( CC_LIST_ENTRY **List )
{
    free( *List );
    return 0;
}

///Intrebare daca se insereaza in List sau daca se insereaza la inceputul listei sau la sfarsitul ei
///Momentan insereaza la finalul listei
int LstInsertValue( CC_LIST_ENTRY *List, ListType Value )
{
    ///Complexitate O(1)
    ///Creez un nou nod si fac legaturile intre el si vecinii lui
    CC_LIST_ENTRY *aux, *newNode;
    aux = List -> Pre;
    newNode = ( CC_LIST_ENTRY * )malloc( sizeof( CC_LIST_ENTRY ) );
    if( newNode == 0 ) return -1;
    newNode -> Value = Value;
    newNode -> Pre = aux;
    newNode -> Urm = List;
    aux -> Urm = newNode;
    List -> Pre = newNode;
    ///Cresc numarul de noduri din lista
    List -> Value = List -> Value + 1;
    return 0;
}

///Intrebare daca e nevoie de List, lista este dublu inlantuita, se pot relationa vecinii lui Node si sterge Node
///Raspuns personal: pentru modificarea numarului de noduri
int LstRemoveNode( CC_LIST_ENTRY *List, CC_LIST_ENTRY *Node )
{
    ///Complexitate O(1)
    Node -> Pre -> Urm = Node -> Urm;
    Node -> Urm -> Pre = Node -> Pre;
    free( Node );
    List -> Value = List -> Value - 1;
    return 0;
}

int LstGetNodeValue( CC_LIST_ENTRY *Node, ListType *Value )
{
    ///Complexitate O(1)
    *Value = Node -> Value;
    return 0;
}

int LstGetNodeCount( CC_LIST_ENTRY *List )
{
    ///Complexitate O(1)
    return List -> Value;
}

int LstGetNthNode( CC_LIST_ENTRY *List, int Index, CC_LIST_ENTRY **Node )
{
    ///Complexitate O(n) worst case
    int n = List -> Value;
    CC_LIST_ENTRY *aux;
    ///Mergem pe drumul cel mai scurt 1->Index sau n->Index
    if( n - Index < Index )
    {
        aux = List -> Pre;
        for( int i = n ; i > Index ; i-- )
        {
            aux = aux -> Pre;
        }
    }
    else
    {
        aux = List -> Urm;
        for( int i = 1 ; i < Index ; i++ )
        {
            aux = aux -> Urm;
        }
    }
    *Node = aux;
    return 0;
}

int LstClear( CC_LIST_ENTRY *List )
{
    ///Complexitate O(n)
    int n = List -> Value;
    CC_LIST_ENTRY *del;
    for( int i = 1 ; i <= n ; i++ )
    {
        LstGetNthNode( List , 1 , &del );
        LstRemoveNode( List , del );
    }
    return 0;
}

int LstMergeSortedList( CC_LIST_ENTRY *Destination, CC_LIST_ENTRY *Source )
{
    ListType *aux = ( ListType * )malloc( sizeof( ListType ) * ( Destination -> Value + Source -> Value ) );
    ListType *aV = ( ListType * )malloc( sizeof( ListType ) * Destination -> Value );
    ListType *bV = ( ListType * )malloc( sizeof( ListType ) * Source -> Value );
    if( aux == 0 || aV == 0 || bV == 0 ) return -1;
    CC_LIST_ENTRY *a = Destination;
    int nr = 0;
    for( int i = 1 ; i <= Destination -> Value ; i++ )
    {
        a = a -> Urm;
        aV[ i - 1 ] = a -> Value;
    }
    a = Source;
    for( int i = 1 ; i <= Source -> Value ; i++ )
    {
        a = a -> Urm;
        bV[ i - 1 ] = a -> Value;
    }
    int A=0,B=0;
    while( A < Destination -> Value || B < Source -> Value )
    {
        if( A == Destination -> Value )
        {
            aux[ nr++ ] = bV[ B++ ];
        }
        else if( B == Source -> Value )
        {
            aux[ nr++ ] = aV[ A++ ];
        }
        else if( aV[ A ] > bV[ B ] )
        {
            aux[ nr++ ] = bV[ B++ ];
        }
        else
        {
            aux[ nr++ ] = aV[ A++ ];
        }
    }
    free( aV );
    free( bV );
    A = Source -> Value + Destination -> Value;
    LstClear( Destination );
    for( int i = 1 ; i <= A ; i++ )
    {
        LstInsertValue( Destination , aux[ i - 1 ] );
    }
    free( aux );
    return 0;
}

int MergeSortLst( ListType *vec , int Left, int Right )
{
    ///Complexitate O(1)
    if( Right - Left == 0 ) return 0;
    int Middle = Left + ( Right - Left ) / 2;
    ///Sortez cele doua jumatati ale vectorului
    if( MergeSortLst( vec , Left , Middle ) == -1 ) return -1;
    if( MergeSortLst( vec , Middle + 1 , Right ) == -1 ) return -1;

    int A = Left, B = Middle + 1, i = 0; /// pentru interclasare se vor folosi indicii A ( jumatatea stanga ) si B ( jumatatea dreapta )
    ListType *aux; /// si un vector auxiliar
    aux = ( ListType * )malloc( ( Right - Left + 1 ) * sizeof( ListType ) );
    if( aux == 0 ) return -1;
    while( A <= Middle || B <= Right )
    {
        ///fac interclasarea a celor doua jumatati
        if( A == Middle + 1 )
        {
            aux[ i++ ] = vec[ B++ ];
        }
        else if( B == Right + 1 )
        {
            aux[ i++ ] = vec[ A++ ];
        }
        else if( vec[ A ] <= vec[ B ] )
        {
            aux[ i++ ] = vec[ A++ ];
        }
        else
        {
            aux[ i++ ] = vec[ B++ ];
        }
    }
    ///copiez in vector auxiliarul si dealoc memoria auxiliarului
    for( int i = Left ; i <= Right ; i++ )
    {
        vec[ i ] = aux[ i - Left ];
    }
    free( aux );
    return 0;
}

int LstSortByValues( CC_LIST_ENTRY *List )
{
    ListType *vec;
    int n = List -> Value;
    vec = ( ListType * )malloc( sizeof( ListType ) * n );
    for( int i = 0 ; i < n ; i++ )
    {
        List = List -> Urm;
        vec[ i ] = List -> Value;
    }
    List = List -> Urm;
    int rasp = MergeSortLst( vec , 0 , n - 1 );
    LstClear( List );
    for( int i = 0 ; i < n ; i++ )
    {
        LstInsertValue( List , vec[ i ] );
    }
    free( vec );
    return rasp;
}

void DisplayList( CC_LIST_ENTRY *List )
{
    int n = List -> Value;
    printf( "\n******\n" );
    for( int i = 1 ; i <= n ; i++ )
    {
        List = List -> Urm;
        int x;
        LstGetNodeValue( List , &x );
        printf( "%d " , x );
    }
    printf( "\n******\n" );
}

int main()
{
    /*
    FILE *fin = fopen( "algsort.in" , "r" );
    FILE *fout = fopen( "algsort.out" , "w" );
    CC_LIST_ENTRY *List,*A;
    LstCreate( &List );
    int i,n,x;
    while( scanf( "%d" , &n ) )
    {
        if( n == 1 )
        {
            scanf( "%d" , &n );
            LstInsertValue( List , n );
        }
        else if( n == 2 )
        {
            printf( "%d\n" , LstGetNodeCount( List ) );
        }
        else if( n == 3 )
        {
            scanf( "%d"  , &n);
            LstGetNthNode( List , n , &A );
            LstGetNodeValue( A , &n );
            printf( "%d\n" , n );
        }
        else if( n == 4 )
        {
            scanf( "%d"  , &n);
            LstGetNthNode( List , n , &A );
            LstRemoveNode( List , A );
        }
        else if( n == 5 )
        {
            DisplayList( List );
        }
        else
        {
            LstSortByValues( List );
        }
    }*/
    FILE *fin = fopen( "algsort.in" , "r" );
FILE *fout = fopen( "algsort.out" , "w" );
    CC_LIST_ENTRY *List,*A;
    LstCreate( &List );
    int i,n,x;
    fscanf( fin , "%d" , &n );
    for( i = 1 ; i <= n ; i++ )
    {
        fscanf( fin , "%d" , &x );
        LstInsertValue( List , x );
    }
    LstSortByValues( List );
    for( i = 1 ; i <= n ; i++ )
    {
        LstGetNthNode( List , i , &A );
        LstGetNodeValue( A , &x );
        fprintf( fout , "%d " ,x );
    }
    fprintf( fout , "\n" );
}