Flop Sorting

Απελπισμένος να συνεισφέρει στο CCO, ο Robert προσπάθησε να εφεύρει ένα πρόβλημα δέντρου τμημάτων. Οι προδιαγραφές για αυτό το πρόβλημα είναι:

"Σας δίνεται μια λίστα με ~N~ διακριτούς ακεραίους μεταξύ του ~1~ και του \(Ν\). Αυτοί είναι διατεταγμένοι σε μια σειρά τέτοια ώστε ο ~i~-οστος ακέραιος από αριστερά να είναι ~a_i~, όπου ~1 \le i \le N~. Ορίζουμε μία πράξη flop σε ένα σύνολο στοιχείων ως εναλλαγή του ελάχιστου στοιχείου του συνόλου με το μέγιστο στοιχείο του συνόλου. Θα υπάρχουν ~Q~ πράξεις flop, καθεμία από τις οποίες καθορίζει δύο αριθμούς ~l~ και ~r~ (~1 \le l \le r \le N~). Για κάθε πράξη, πρέπει να εκτελέσετε ένα flop στο διάστημα [~l~, ~r~] (δηλαδή στο τμήμα των αριθμών ~a_l, a_{l+1}, . . . , a_{r-1}, a_r~). Εσείς πρεπει να εκτελέστε τα ~Q~ flops με τη σειρά που δίνεται και να αναφέρετε το τελικό αποτέλεσμα."

Τώρα που τελείωσε με τη δήλωση του προβλήματος, ο Robert πρέπει να δημιουργήσει κάποια δεδομένα δοκιμής. Για μια περίπτωση δοκιμής συγκεκριμένα, προσπαθεί να κωδικοποιήσει ένα εσωτερικό αστείο (inside joke) στην αρχική και την τελική ακολουθία των αριθμών. Με αυτές τις δύο ακολουθίες σταθερές, βοηθήστε τον να βρει οποιαδήποτε ακολουθία πράξεων flop που μετατρέπει την πρώτη ακολουθία στη δεύτερη.

Είσοδος

Η πρώτη γραμμή θα περιέχει τον ακέραιο ~N~ (~1 \le N \le 4096~). Η δεύτερη γραμμή θα περιέχει ~N~ διακριτούς, χωρισμένους με κενό, ακέραιους μεταξύ του ~1~ και του ~N~, που αντιπροσωπεύουν την αρχική ακολουθία. Η τρίτη γραμμή επίσης θα περιέχει ~N~ διακριτούς, χωρισμένους με κενό, ακέραιους μεταξύ του ~1~ και του ~N~, που αντιπροσωπεύουν την τελική ακολουθία.

Έξοδος

Η πρώτη γραμμή της εξόδου θα πρέπει να περιέχει τον ακέραιο ~Q~, με ~Q \le 300\,000~. Οι επόμενες ~Q~ γραμμές θα πρέπει να περιέχουν δύο ακέραιους ~l~ και ~r~ με ~1 \le l \le r \le N~.

Βαθμολογία

Για ~5~ από τους ~25~ διαθέσιμους βαθμούς, ~N \le 100~. Για επιπλέον ~10~ από τους ~25~ διαθέσιμους βαθμούς, ~N \le 2048~.

Παράδειγμα

input

6
1 3 5 6 4 2
1 2 3 4 5 6

output

4
2 3
3 6
2 5
4 5

Επεξήγηση του παραδείγματος

Η πρώτη πράξη flop ανταλάσσει το ~3~ και το ~5~, η δεύτερη πράξη flop ανταλάσσει το ~6~ και το ~2~, η τρίτη πράξη flop ανταλάσσει το ~5~ και το ~2~ και η τέταρτη πράξη flop ανταλάσσει το ~5~ και το ~4~.