Toată lumea ştie că Mirel are 2*N sticluţe cu parfum aşezate pe un raft cu 2*N poziţii, numerotate de la 1 la 2*N. El are N sticluţe cu parfum cumpărate din ţară şi alte N sticluţe cu parfum cumpărate din Franţa. Sticluţele cumpărate din ţară sunt etichetate cu r1, r2, …, rN, iar sticluţele cumpărate din Franţa sunt etichetate cu f1, f2, …, fN. Fiecare sticluţă are asociată valoarea cu care a fost cumpărată.
Iniţial, Mirel are aşezate pe primele N poziţii sticluţele cumpărate din ţară sortate crescător după valoare, iar pe următoarele N poziţii sticluţele cumpărate din Franţa sortate tot crescător după valoare. Astfel, cele 2*N sticluţe cu parfum sunt aşezate în felul următor: r1, r2, …, rN, f1, f2, …, fN. Mai exact, sticluţa ri se află pe poziţia i, iar sticluţa fi se află pe poziţia N+i, pentru i din intervalul [1, N].
Prietenul său cel mai bun, Marian, s-a gândit să-i facă o surpriză şi să-i schimbe aranjarea sticluţelor cu parfum în următoarea ordine: r1, f1, r2, f2, …, rN, fN. Cum Marian are două mâini, el poate face numai următorul tip de operaţie: ia două sticluţe cu parfum de pe raft (de pe două poziţii diferite) şi le interschimbă.
Cerinţă
Dându-se numărul N şi 2*N valori reprezentând valoarea fiecărei sticluţe cu parfum, ajutaţi-l pe Marian să facă operaţiile necesare pentru a schimba ordinea sticluţelor cu parfum în ordinea precizată în enunţ.
Date de intrare
Fişierul de intrare aranjare2.in conţine pe prima linie numărul N, iar pe următoarea linie 2*N numere naturale, separate prin câte un spaţiu. Primele N numere reprezintă valorile sticluţelor cumpărate din ţară, iar următoarele N numere reprezintă valorile sticluţelor cumpărate din Franţa. Atât primele N, cât şi ultimele N numere sunt sortate crescător în funcţie de valoare.
Date de ieşire
Fişierul de ieşire aranjare2.out va conţine mai multe linii. Pe fiecare linie se vor afla două numere diferite x şi y din intervalul [1, 2*N], semnificând faptul că Marian trebuie să interschimbe sticluţa de pe poziţia x cu sticluţa de pe poziţia y.
Restricţii
• 2 ≤ N ≤ 31 000
• Dacă există mai multe soluţii, se poate afişa oricare dintre ele.
• Soluţia nu trebuie să facă neapărat numărul minim de operaţii.
Exemple
aranjare2.in
aranjare2.out
Explicaţii
3
1 3 5 2 3 5
2 4
3 5
3 4
În explicaţia de mai jos, fiecare sticluţă are numele etichetei urmat de valoarea ei în paranteză.
Şirul iniţial este: r1(1) r2(3) r3(5) f1(2) f2(3) f3(5)
După prima mutare devine: r1(1) f1(2) r3(5) r2(3) f2(3) f3(5)
După a doua mutare devine: r1(1) f1(2) f2(3) r2(3) r3(5) f3(5)
După ultima mutare devine: r1(1) f1(2) r2(3) f2(3) r3(5) f3(5)