sort2dist

Jocul pe care îl joacă Robo atunci când se plictisește este un joc inteligent pentru roboței. Pe ecranul tabletei lui roboțești, sunt $N$ căsuțe de formă pătrată, cu latura egală cu $1$. Căsuțele sunt așezate pe un rând, una lângă alta, fiind etichetate, în această ordine, cu numere de la $1$ la $N$. Fiecare căsuță conține câte un număr natural, identificatorul câte unuia dintre prietenii săi, roboței, ca și el. Identificatorii se pot repeta.

Robo poate interschimba conținutul a două căsuțe, numai dacă distanța acestora pe orizontală este egală cu distanța dintre brațele sale; distanța, pe orizontală, dintre centrele a două căsuțe etichetate cu $i$, respectiv cu $j$ este $j-i$ ($1 \le i < j \le N$). El își poate fixa în orice moment distanța dintre brațe la $1$ sau își poate dubla distanța curentă dintre brațe, de oricâte ori este necesar, fără a depăși valoarea $N-1$. Astfel, distanța dintre brațele sale poate fi $1$, apoi, prin dublare, $2$, apoi, prin dublare $4$, apoi, prin dublare $8$ etc.

La începutul jocului, distanța dintre brațele lui Robo este $1$. De fiecare dată când consideră convenabilă distanța dintre brațe, realizează o interschimbare.

Cerință

Se cere ca Robo să așeze identificatorii în căsuțe în ordine crescătoare, prin maximum $12500$ interschimbări de tipul celei precizate mai sus.

Date de intrare

Fișierul sort2dist.in conține:

• pe prima linie numărul natural $N$, cu semnificația din enunț;
• pe următoarele $N$ linii, $N$ numere, reprezentând, în această ordine, identificatorii conținuți în căsuțele tabletei (identificatorul de pe linia $i$ este conținut de căsuța $i-1$).

Date de ieșire

Fișierul sort2dist.out conține:

• pe prima linie un număr natural $M$, reprezentând numărul de interschimbări realizate de Robo (nu neapărat numărul minim de interschimbări necesare);
• pe fiecare dintre următoarele $M$ linii (doar dacă $M$ este nenul), câte două numere naturale, separate prin câte un spațiu, reprezentând etichetele căsuțelor al căror conținut s-a interschimbat, în ordinea realizării acestor interschimbări.

Restricții și precizări

• $1 \le N \le 1 \ 000$;
• identificatorii sunt numere naturale de maximum $30$ de cifre;
• pentru $25\%$ din punctaj, fișierele de test conțin numere cu maximum $18$ cifre;
• pentru $25\%$ din punctaj, $N \le 100$.

Exemplu

sort2dist.in

4
5
7
6
2

sort2dist.out

2
2 4
2 1

Explicație

Tableta are $4$ căsuțe, conținând, în această ordine, identificatorii $(5, 7, 6, 2)$.
Pentru ordonarea crescătoare s-au realizat $2$ interschimbări:

• s-a interschimbat conținutul căsuțelor $2$ și $4$ (distanța dintre centrele lor fiind $2$), identificatorii din căsuțe fiind acum $(5, \underline{2}, 6, \underline{7})$;
• s-a interschimbat conținutul căsuțelor $1$ și $2$ (distanța dintre centrele lor fiind $1$), identificatorii din căsuțe fiind acum $(\underline{2}, \underline{5}, 6, 7)$, ordonați crescător.