Va reamintesc faptul ca as dori sa includeti ideea de rezolvare drept
comentariu in interiorul sursei.

   Ii multumesc in acest sens lui Bogdan Dumitru, a carui sursa o aveti
mai jos, si care prin comentariul lui, m-a scutit sa prezint eu rezolvarea
problemei ;-) De altfel algoritmul meu de rezolvare coincide cu cel aplicat
de voi, presupunand un numar de 2*n operatii.

   Deci:

 O scurta explicatie a rezolvarii.
  Pentru inceput, as dori sa remarc faptul ca problema a mai fost propusa
 o data, la un concurs PACO (in '98, parca). Daca nu ma insel, acolo nu
 era permisa fixarea elementelor fictive 0 si N+1, ceea ce complica putin
 lucrurile. Oricum, cele 2 rezolvari au multe puncte comune.
  Deci : pentru inceput, sortez o copie a vectorului, pastrand de asemenea
 si indicii initiali. Determin astfel, pentru fiecare element al vectorului
 initial, pozitia sa in sirul final (sirul sortat crescator).
  Localizez minimul si fixez elementul din dreapta lui, aducandu-l astfel
 pe prima pozitie.
  Apoi procedez inductiv : sa presupunem ca am reusit sa aduc primele K
 elemente ale vectorului pe primele K pozitii, sortate DEScrescator, ca
 mai jos.

                       restul elementelor
    K K-1 K-2 ... 1 |______________________|

  Acum incerc sa aduc si al K+1 - lea element. Aceasta se face
 astfel :
  - il localizez (sa spunem ca el se afla pe pozitia P);

    K K-1 K-2 ... 1 |______| P |___________|

  - fixez pozitia P, ceea ce duce la configuratia urmatoare :

    |______| 1 2 ... K-1 K-2 P |___________|

  - fixez pozitia P+1, obtinand un nou vector, in care primele K+1 elemente
 ale sale apar pe primele K+1, sortate tot descrescator :

    P K K-1 K-2 |__________________________|

                adica

    K+1 K K-1 K-2 |________________________|

  Rezolvarea este acum (cred) evidenta : K ia valori de la 2 la N si pentru
 fiecare K, se efectueaza pasii de mai sus. Se obtine un vector sortat
 descrescator. Se fixeaza apoi pozitia N+1, ceea ce inverseaza sensul
 sortarii.
  Cateva observatii :
  - acest algoritm efectueaza intotdeauna exact 2*N fixari;
  - numarul de fixari ar putea fi micsorat (uneori - de pilda pe exemplul
 din problema - se fixeaza aceeasi pozitie de mai multe ori consecutiv,
 ceea ce evident duce la aceeasi configuratie; din motive de lene :-) nu am
 eliminat acest 'bug';
  - complexitate :
    - sortarea initiala este O(N*logN);
    - se fac N localizari; o localizare este O(N), deci O(N^2);
    - se fac 2*N fixari; o fixare este O(N), deci O(N^2);
    Algoritmul este deci patratic, o complexitate acceptabila pentru
  limitele date.