#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;

ifstream f("algsort.in");
ofstream g("algsort.out");

template <class X , int SIZE=1024> class Vect
{
    X *ZonaFolosita;
    int SizeF;
    X *ZonaAlocata;
    int SizeA;

public:
    Vect();
    int getSizeF() {return SizeF;}
    int getSizeA() {return SizeA;}
    void add(X ob);
    X &operator[] (int i);
    void deleteFinal();
    void deletePoz(int poz);
    void merge_Arrays (int l, int m, int h);
    void afisare();
    void cautare(X ob);
    void merge_Sort (int l, int r);
};

template <class X, int SIZE>
Vect <X,SIZE>::Vect()           //Vect::Vect()
{
    ZonaFolosita=new X[0];
    ZonaAlocata =new X[SIZE];
    SizeA=SIZE;
    SizeF=0;
}

template <class X, int SIZE>
X& Vect <X,SIZE>:: operator[](int i)
{
    if(i<0 || i>=SizeF)
    {
        cout<<"\n\nNu puteti accesta un element de pe pozitia: "<<i<<"!\n";
        exit(0);
    }
    return ZonaFolosita[i];
}

template <class X, int SIZE> void
Vect <X,SIZE>::add(X ob)
{
    if(SizeF<SizeA)
    {
        SizeF++;
        ZonaFolosita=(X *)realloc(ZonaFolosita , SizeF * sizeof(X));

        ZonaFolosita[SizeF-1] = ob;

        memcpy(ZonaAlocata, ZonaFolosita, SizeF * sizeof(X));
        ZonaAlocata =(X *)realloc(ZonaAlocata , SizeA * sizeof(X));
    }
    else
    {
        SizeA= 2* SizeA;
        ZonaAlocata =(X *)realloc(ZonaAlocata , SizeA * sizeof(X));
        SizeF++;
        ZonaFolosita=(X *)realloc(ZonaFolosita , SizeF * sizeof(X));
        ZonaFolosita[SizeF-1] = ob;
        memcpy(ZonaAlocata, ZonaFolosita, SizeF * sizeof(X));
        ZonaAlocata =(X *)realloc(ZonaAlocata , SizeA * sizeof(X));
    }

}

template <class X , int SIZE> void
Vect <X,SIZE>:: deleteFinal()
{
    SizeF--;
    X *temp;
    temp = (X *)malloc (SizeF * sizeof(X));
    memcpy(temp, ZonaFolosita , SizeF * sizeof(X));
    delete ZonaFolosita;

    ZonaFolosita= (X *)malloc(SizeF * sizeof(X));
    memcpy(ZonaFolosita , temp , SizeF * sizeof(X));

    memcpy(ZonaAlocata , ZonaFolosita , SizeF * sizeof(X));
    ZonaAlocata= (X *)realloc(ZonaAlocata , SizeA * sizeof(X));

}

template <class X , int SIZE> void
Vect <X,SIZE>:: deletePoz(int poz)
{
    int i;
    for(i=poz;i<SizeF-1;i++)
        ZonaFolosita[i]=ZonaFolosita[i+1];
    deleteFinal();
}

template <class X, int SIZE> void
Vect <X,SIZE>:: merge_Arrays (int l, int m, int h)
{
    X left [250005];
    X right [250005];
    int i, j, k, nl, nr;
    nl = m - l + 1; // nl - nr of elements in left array
    nr = h - m; //nr - nr of elements in right array

    for (i = 0; i < nl; ++ i) //v [m] is taken
    {
        left [i] = ZonaFolosita [l + i];
    }

    for (i = 0; i < nr; ++ i) //v [m] is not taken
    {
        right [i] = ZonaFolosita [m + i + 1];
    }

    i = j = 0;
    k = l; // k - iterator for the original array
    while (i < nl && j < nr)
    {
        if (left [i] <= right [j])
        {
            ZonaFolosita [k] = left [i ++];
        }
        else
        {
            ZonaFolosita [k] = right [j ++];
        }
        k ++;
    }


    while (i < nl)
    {
        ZonaFolosita [k ++] = left [i ++];
    }
    while (j < nr)
    {
        ZonaFolosita [k ++] = right [j ++];
    }

}

template <class X, int SIZE>
void Vect <X,SIZE> :: merge_Sort (int l, int r)
{
    if (l == r) return;

    int m = (l + r) / 2;

    merge_Sort (l, m);
    merge_Sort (m + 1, r);
    merge_Arrays (l, m, r);


}



template <class X, int SIZE> void
Vect <X,SIZE>:: afisare()
{
    /*cout<<"Dimensiunea Zonei Folosite este: "<<SizeF;
    cout<<"\nDimensiunea Zonei Alocate este: "<<SizeA;
    cout<<"\nElementele Zonei Folosite sunt: ";*/
    for(int i=0;i<SizeF;i++)
        g<<ZonaFolosita[i]<<" ";
    //cout<<endl<<endl;
}

template <class X, int SIZE> void
Vect <X,SIZE>:: cautare(X ob)
{
    int ok=0,i;
    for(i=0;i<SizeF&&ok==0;i++)
        if(ZonaFolosita[i]==ob)
                ok=1;
    if(ok==1)
        cout<<"Elementul este gasit pe pozitia: "<<i-1<<endl;
    else
        cout<<"Elementul nu exista!\n";

}

int main()
{
    Vect<int, 500000> p;
    int n,x;
    f>>n;
    for(int i=0;i<n;i++)
    {
        f>>x;
        p.add(x);
    }
    p.merge_Sort(0 , n-1);
    p.afisare();

    return 0;
}