Iacob Tudor (IacobTudor) Cerința
Dr. Le Quack , fiind un mare fan al Lord Of The Rings , decide să plece în Mordor , locul unde a fost făurit inelul atotputernic . Când acesta ajunge la turnul lui Sauron , observă că intrarea are un cifru . Cifrul este un șir de numere întregi. Dr. Le Quack poate aplică următorul algoritm șirului :
for(int i=1;i<n;i++){
if(a[i]<=a[i+1]){
swap(a[i], a[i+1]);
}
}
Dr. Le Quack poate aplica acest tip de operatie de un număr nelimitat de ori ( posibil 0 ). Intrarea se va deschide atunci când șirul va fi unul descrescator. Un șir este descrescător dacă pentru fiecare i din intervalul [1 , n-1] se respectă condiția a[i] ≥ a[i+1]. Dr. Le Quack fiind lacom vrea să stie care este numărul minim operații pentru a deschide intrarea. Pentru că acesta a chiulit de la orele de informatică uitat cum se rezolvă problemele de natură algoritmica , vă roaga sa îl ajutați în schimbul a 100 de puncte și asigurare medicală la cabinetul său.
Date de intrare
Fișierul de intrare mordortrip.in conține pe prima linie numărul n, iar pe a doua linie n numere întregi separate prin spații.
Date de ieșire
Fișierul de ieșire mordortrip.out conține pe prima linie un număr ans reprezentând numărul minim de operații ale
algoritmului specificat mai sus pentru a sorta vectorul dat la input într-unul descrescător.
Restricții și precizări
- Numerele sunt întregi , din intervalul
[ -1.000.000.000 , 1.000.000.000 ],NUneapărat distincte. - Se garantează că avem mereu soluție dintr-un număr finit de operații ale algoritmului descris.
- Pentru teste în valoare de
20 de puncte , N ≤ 5.000. - Pentru restul testelor ,
N ≤ 1.000.000.
Exemplu:
mordortrip.in
5 5 1 3 2 4
mordortrip.out
3
mordortrip.in
4 3 1 2 2
mordortrip.out
1
Explicație
În primul exemplu , sunt necesare doar 3 aplicări ale algoritmului : 1 – 5 3 2 4 1 ; 2 – 5 3 4 2 1 ; 3 – 5 4 3 2 1