Se dă un şir de N numere naturale, care trebuie ordonat crescător. Singura operaţie permisă este să consideraţi elementele de pe poziţiile i, i+1, ..., j (pentru i şi j arbitrare, i<j), şi să inversaţi ordinea acestor elemente (adică elementul de pe poziţia i ajunge pe poziţia j, i+1 ajunge pe poziţia j-1, ..., j ajunge pe poziţia i). Costul unei astfel de operaţii este numărul de elemente din subşirul inversat, şi anume j-i+1.
Cerinţă
Scrieţi un program care să determine o secvenţă de operaţii care ordonează crescător şirul dat şi are un cost total cât mai mic (dar nu obligatoriu minim).
Date de intrare
Fişierul de intrare invsort.in conţine pe prima linie numărul N, şi apoi N linii cu elementele şirului dat (nu neapărat distincte).
Date de ieşire
Fişierul de ieşire invsort.out va conţine pe fiecare linie descrierea unei operaţii. O operaţie este descrisă prin numerele i şi j, separate printr-un spaţiu. Aceste numere satisfac 1 <= i < j <= N.
Restricţii
• 2 <= N <= 32000
• valorile şirului care trebuie ordonat sunt între 0 şi 31999
Punctaj
• dacă şirul de operaţii (executate în ordinea din fişierul de ieşire) nu ordonează intrarea, primiţi 0 puncte
• în cazul în care costul total este cel mult 4000000 (patru milioane) primiţi punctaj maxim
• în cazul în care costul total este cel mult 40000000 (patruzeci de milioane) primiţi 40% din punctajul pe test
• în 50% din teste şirul de intrare conţine numai elemente de 0 şi 1
• pentru toate testele folosite la corectare, N=32000
Exemple
invsort.in
invsort.out
Explicaţii
5
1
0
1
1
0
5
1
0
1
1
0
• prima operaţie are efectul: 1 0 [1 1 0] -> 1 0 0 1 1
• a doua operaţie are efectul: [1 0 0] 1 1 -> 0 0 1 1 1
• costul total este 3 + 3 = 6