Primaria oraşului ONI a făcut un contract cu firma Gigel.SRL în vederea amenajării gardului Grădinii Botanice. Şeful firmei a constatat că gardul cu pricina este format doar din trei tipuri de scânduri care sunt aranjate fără nicio regulă. Fiind un tip cu „gust estetic” şi-a propus să rearanjeze scândurile astfel încât gardul să conţină scândurile grupate astfel: primele să fie scândurile de primă dimensiune (cea mai mică) apoi cele mijlocii, iar ultimele să fie cele de dimensiunea cea mai mare. Echipa care a fost desemnată să execute lucrarea are un singur muncitor care doreşte să ştie care este numărul minim de schimbări pe care ar trebui să le facă astfel încât să rezolve problema şi scândurile să fie ordonate aşa precum a decis şeful firmei. Operaţia de schimbare constă în alegerea a două scânduri diferite şi aşezarea uneia în locul celeilalte.
Cerință
Dându-se un număr ce reprezintă numărul de scânduri care alcătuiesc gardul, precum şi modul în care sunt aranjate scândurile în gard, să se determine care este numărul minim de schimbări ce trebuie realizat astfel încât gardul să aibă scândurile aranjate crescător. Scândurile sunt codificate în funcţie de dimensiune prin valorile , şi .
Date de intrare
Fişierul sort.in conţine pe prima linie un număr natural . Pe a doua linie sunt valori , sau separate prin câte un spaţiu ce reprezintă modul de aşezare a scândurilor în gardul grădinii.
Date de ieșire
Fişierul sort.out va conţine un număr care reprezintă numărul minim de schimbări ce trebuie realizate pentru a aranja gardul astfel încât să fie ordonat crescător.
Restricții și precizări
Exemplu
sort.in
10
1 3 1 2 2 3 1 3 2 1
sort.out
3
Explicație
- se realizează schimbarea valorilor de pe poziţiile cu , apoi cu şi cu .
- astfel va rezulta succesiv: