Неугомонная маленькая разбойница любит наблюдать за испугом животных в своём зверинце. Однажды ей вздумалось выстроить их по неубыванию роста. Когда она им приказала выстроиться, они настолько перепугались, что сделали это неправильно.
Маленькая разбойница рассердилась было, но ей вдруг пришла в голову странная затея. Она решила попробовать сама расставить зверей как надо. Для этого она иногда называет числа l и r, такие что число r - l + 1 чётно. После этого все звери, стоящие на позициях с l по r включительно, меняются местами: зверь на позиции l меняется со зверем на позиции l + 1, зверь на позиции l + 2 меняется со зверем l + 3, ..., наконец, зверь на позиции r - 1 меняется со зверем r.
Помогите маленькой разбойнице расставить всех животных в порядке неубывания роста. Вам нужно назвать не более 20 000 отрезков, так как после совершения слишком большого количества операций маленькой разбойнице надоест, и она начнёт снова пугать зверей.
Выходные данные
Выведите последовательность действий, которая расположит зверей в порядке неубывания роста.
В ответе должно быть записано несколько строк, i-ая из которых должна содержать два числа li и ri через пробел (1 ≤ li < ri ≤ n) — описания отрезков, которые должна называть маленькая разбойница. Отрезки должны быть записаны в порядке применения операций.
Количество операций не должно превышать 20 000.
Если звери стоят в порядке неубывания роста изначально, разрешается не выводить ничего.
Примечание
Обратите внимание, что не требуется минимизировать число совершённых операций. Достаточно, чтобы их было не больше 20 000.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 1 4 3
|
1 4
|
|
2
|
7
36 28 57 39 66 69 68
|
1 4
6 7
|
|
3
|
5
1 2 1 2 1
|
2 5
3 4
1 4
1 4
|