#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 quicksort(int left, int right);
    void afisare();
    void cautare(X ob);
};

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>:: quicksort(int left, int right)
{
    int rand;
    int mini=rand%(right + left);

    int i = left;
    int j = right;
    int pivot = ZonaFolosita[mini];

    while(left<j || i<right)
    {
        while(ZonaFolosita[i]<pivot)
        i++;
        while(ZonaFolosita[j]>pivot)
        j--;

        if(i<=j){
                X temp = ZonaFolosita[i];
                ZonaFolosita[i] = ZonaFolosita[j];
                ZonaFolosita[j] = temp;
            i++;
            j--;
        }
        else{
            if(left<j)
                quicksort(left, j);
            if(i<right)
                quicksort(i,right);
            return;
        }
    }
}


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,500001> p;
    int n,x;
    f>>n;
    for(int i=0;i<n;i++)
    {
        f>>x;
        p.add(x);
    }
    p.quicksort(0 , n-1);
    p.afisare();

    return 0;
}