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

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$.

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

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.

Pe prima linie a fişierului sortare.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

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

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

h2. Restricţii

* $1 ≤ N ≤ 100000$

* $1 ≤ N ≤ 200000$

h2. Exemplu

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ă.

Explicaţie: În cazul primului exemplu putem forma $3$ subşiruri: $(4)$, $(1, 2)$, $(3)$. Putem pune subşirul $(3)$ la finalul subşirului $(4)$ ş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") ==