| Fişierul intrare/ieşire: | sortare2.in, sortare2.out | Sursă | PreOJI 2017 |
| Autor | Marius Nicoli | Adăugată de |  Popa Mihai •mihaipopa12 |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 12288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Sortare 2
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.
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.
Date de ieşire
Pe prima linie a fişierului sortare2.out se află un număr ce reprezintă costul minim cerut.
Restricţii
- 1 ≤ N ≤ 100000
Exemplu
| sortare2.in | sortare2.out |
|---|---|
| 4 4 1 3 2 | 2 |
| 4 1 2 3 4 | 0 |
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ă.
