Вася — учитель физкультуры в школе. В отличие от других учителей физкультуры, Вася не любит когда ученики выстраиваются в шеренгу по росту. Вместо этого, он требует, чтобы дети выстраивались в порядке a1, a2, ..., an, где ai — рост i-го ученика в шеренге, а n — количество учеников в шеренге. Детям сложно запомнить этот странный порядок, и сегодня они выстроились в порядке b1, b2, ..., bn, что очень расстроило Васю. Теперь Вася хочет переставить детей так, чтобы получился порядок a1, a2, ..., an. За одно действие Вася может поменять местами двух человек, стоящих подряд в шеренге. Помогите Васе — составьте последовательность обменов, приводящую к нужной Васе расстановке. Количество действий минимизировать не требуется.
Выходные данные
В первой строке выведите целое число k (0 ≤ k ≤ 106) — количество действий. Минимизировать k не требуется, но оно не должно превосходить 106. Далее выведите k строк по два целых числа через пробел. Строка pi, pi + 1 (1 ≤ pi ≤ n - 1) означает, что Вася должен поменять местами учеников на местах pi и pi + 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2 3 2
3 2 1 2
|
4
2 3
1 2
3 4
2 3
|
|
2
|
2
1 100500
1 100500
|
0
|