== include(page="template/taskheader" task_id="sortare") ==

Sortarea rapida (sau quicksort) este un bine cunoscut algoritm de sortare. Algortimul opereaza astfel:

Sortarea rapida (sau QuickSort) este un bine cunoscut algoritm de sortare. Algortimul functioneaza astfel:

* Se alege un element din sir, care se va numit pivot
* Se reordoneaza sirul astfel incat toate elementele care detin o valoare mai mica decat valoarea elementului pivot se vor pozitiona inaintea elementului pivot, si elementele care au o valoare mai mare decat valoarea elementului pivot se vor pozitiona dupa elementul pivot
* Se sorteaza recursiv cele doua bucati din sir

Cazul de baza a unei recursivitati sunt listele de dimensiune $0$ sau $1$. Putem descrie in pseudocod acest algoritm astfel:

Cazul de baza a unei recursivitati sunt listele de dimensiune $0$ sau $1$. Putem implementa in pseudocod acest algoritm astfel:

==code(c)|functie qsort(sir[])

 var stanga, dreapta, pivot

 var stanga[], dreapta[], pivot

 daca lungimea(sir) <= 1
   returneaza sir
 pivot = un element din sir

 returneaza concatenaeza(qsort(stanga), pivot, qsort(dreapta))
==

Fumeanu a implementat acest algoritm si considera ca implementarea lui este foarte eficienta. Nargy este mai intelept si isi da seama ca performanta intregului algoritm depinde de modul in care se selecteaza pivotul. Metoda folosita de Fumeanu este urmatoarea: pentru un sir de lungime $i$ el alege mediana elementelor de pe pozitiile $A{~i~}, B{~i~}$ si $C{~i~}$ (mediana reprezinta elementul mijlociu ca marime dintre cele $3$).
Ajutati-l pe Nargy sa gaseasca o permutare a numerelor de la $1$ la $N$ pentru care implementarea lui Fumeanu are adancimea recursivitatii maxima.
 
 

h2. Date de intrare

Fisierul de intrare $sortare.in$ ...

Fisierul de intrare $sortare.in$ contine pe prima linie numarul $N$. Pe urmatoarele $N-1$ linii se vor gasi cate 3 numere natural $A{~i~} B{~i~} C{~i~}$ separate prin spatii ({$2≤i≤N$}).

h2. Date de iesire

In fisierul de iesire $sortare.out$ ...

In fisierul de iesire $sortare.out$ se va scrie pe prima linie $HMax$ reprezentand adancimea maxima a recursivitatii. Pe urmatoarea linie se vor scrie $N$ numere naturale reprezentand o permutare a numerelor de la $1$ la $N$ pentru care se obtine aceasta adancime.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 5.000$
* $1 ≤ A{~i~},B{~i~},C{~i~} ≤ i$

h2. Exemplu
table(example). |_. sortare.in |_. sortare.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 1 2 2
1 2 3
1 3 4
1 3 5
| 3
1 2 3 4 5

|
h3. Explicatie