invsort

Cerință

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, \dots, 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$, $\dots$, $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$.

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 \leq i < j \leq N$.

Restricții și precizări

• $2 \leq N \leq 32 \ 000$
• valorile şirului care trebuie ordonat sunt între $0$ şi $31 \ 999$
• 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 $4 \ 000 \ 000$ (patru milioane) primiţi punctaj maxim
• în cazul în care costul total este cel mult $40 \ 000 \ 000$ (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 = 32 \ 000$

Exemplu

invsort.in

5
1
0
1
1
0

invsort.out

3 5
1 3

Explicație

• prima operaţie are efectul: $1 \ 0 \ [1 \ 1 \ 0] \rightarrow 1 \ 0 \ 0 \ 1 \ 1$
• a doua operaţie are efectul: $[1 \ 0 \ 0] \ 1 \ 1 \rightarrow 0 \ 0 \ 1 \ 1 \ 1$
• costul total este $3 + 3 = 6$