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

Poveste şi cerinţă...

Se da un şir cu $N$ numere care conţine exact o dată toate numerele de la $1$ la $N$ (o permutare a mulţimii $1, 2 ... N$). Dorim sortarea şirului dat în două etape.
În etapa $1$ se împarte şirul în subşiruri, astfel încât fiecare element al şirului iniţial să aparţină exact unui subşir. Elementele din cadrul aceluiaşi subşir trebuie să aibă aceeaşi ordine relativă ca în şirul iniţial. În etapa a doua, din subşirurile existente la un moment dat, se aleg două, se pune unul dintre ele în continuarea celuilalt, apoi cele două şiruri alese sunt eliminate şi pus în locul lor cel rezultat. Pentru fiecare astfel de operaţie realizată în etapa a doua, costul este $1$.
 
Determinaţi costul total minim necesar pentru a sorta crescător şirul dat în modul descris mai sus.

h2. Date de intrare

Fişierul de intrare $sortare2.in$ ...

Pe prima linie a fişierului $sortare2.in$ se găseşte un număr natural $N$, reprezentând dimensiunea permutării. Pe linia a 2-a se găsesc elementele permutării separate prin câte un spaţiu.

h2. Date de ieşire

În fişierul de ieşire $sortare2.out$ ...

Pe prima linie a fişierului $sortare2.out$ se află un număr ce reprezintă costul minim cerut.

h2. Restricţii

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

* $1 ≤ N ≤ 100000$

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

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

| 4
  4 1 3 2
| 2 |
| 4
  1 2 3 4
| 0
|

h3. Explicaţie

...

Explicaţie: În cazul primului exemplu putem forma $3$ subşiruri: $(4)$, $(1, 2)$, $(3)$. Putem pune subşirul $(4)$ la finalul subşirului $(3)$ şi rămân subşirurile: $(1, 2)$, $(3, 4)$. Apoi, punând şirul $(3, 4)$ la finalul şirului $(1, 2)$ obţinem permutarea sortată.

== include(page="template/taskfooter" task_id="sortare2") ==
 

== include(page="template/taskfooter" task_id="sortare2") ==