Fişierul intrare/ieşire:sortare2.in, sortare2.outSursăPreOJI 2017
AutorMarius NicoliAdăugată demihaipopa12Popa Mihai mihaipopa12
Timp execuţie pe test0.05 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultateN/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.insortare2.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ă.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?