/**
Sortare prin insertie

Daca la un moment dat primele i-1 elemente sunt sortate, pentru a insera al i-lea
element si sa ajungem in starea cu primele i sortate, e suficient ca pe el sa il
comparam cu elementele de la finalul secventei sortate.
        i
2 6 8 9 7

compar pe v[i] (7) cu 9 si 8, pe acestea le deplasez o pozitie la dreapta
si il pun pe v[i] dupa primul element care este mai mic ca el.

Pe cazul cel mai defavorabil, adica sirul sortat descrescator, se fac n*(n-1)/2
interschimbari pentru ca fiecare element trebuie dus in fata de tot si ajunge
sa se interschimbe cu toate celelalte.

Insa daca sirul e sortat, al doilea while e foarte scurt (doar se verifica conditia
si este falsa de la inceput).

In acel caz ajungem, ca si la bubble sort la o(n)
insa in cazul cel mai defavorabil avem n^2.

**/
#include <fstream>

using namespace std;
int v[500001];
int n, i, j, aux;
int main () {
    ifstream fin("algsort.in");
    ofstream fout("algsort.out");

    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i];

    /// consideram ca primul estement este un "sir sortat" si aplicam
    /// strategia descrisa

    for (i=2;i<=n;i++) {
        /// am sirul sortat cu primele i elemente si inserez in el pe v[i]
        /// stransformandu-l in sir sortat cu primele i elemente, adica
        /// pregatind pasul urmator
        aux = v[i];
        j = i-1;
        while (j > 0 && v[j] > aux) {
            v[j+1] = v[j];
            j--;
        }
        v[j+1] = aux;
    }


    for (i=1;i<=n;i++)
        fout<<v[i]<<" ";


    return 0;
}