B. Зверинец маленькой разбойницы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Неугомонная маленькая разбойница любит наблюдать за испугом животных в своём зверинце. Однажды ей вздумалось выстроить их по неубыванию роста. Когда она им приказала выстроиться, они настолько перепугались, что сделали это неправильно.

Маленькая разбойница рассердилась было, но ей вдруг пришла в голову странная затея. Она решила попробовать сама расставить зверей как надо. Для этого она иногда называет числа l и r, такие что число r - l + 1 чётно. После этого все звери, стоящие на позициях с l по r включительно, меняются местами: зверь на позиции l меняется со зверем на позиции l + 1, зверь на позиции l + 2 меняется со зверем l + 3, ..., наконец, зверь на позиции r - 1 меняется со зверем r.

Помогите маленькой разбойнице расставить всех животных в порядке неубывания роста. Вам нужно назвать не более 20 000 отрезков, так как после совершения слишком большого количества операций маленькой разбойнице надоест, и она начнёт снова пугать зверей.

Входные данные

В первой строке записано одно целое число n (1 ≤ n ≤ 100) — количество зверей у маленькой разбойницы.

В второй строке через пробел записано n чисел a1, ..., an (1 ≤ ai ≤ 109), где ai — высота зверя, изначально стоящего на i-м месте.

Выходные данные

Выведите последовательность действий, которая расположит зверей в порядке неубывания роста.

В ответе должно быть записано несколько строк, i-ая из которых должна содержать два числа li и ri через пробел (1 ≤ li < ri ≤ n) — описания отрезков, которые должна называть маленькая разбойница. Отрезки должны быть записаны в порядке применения операций.

Количество операций не должно превышать 20 000.

Если звери стоят в порядке неубывания роста изначально, разрешается не выводить ничего.

Примеры
Входные данные
4
2 1 4 3
Выходные данные
1 4
Входные данные
7
36 28 57 39 66 69 68
Выходные данные
1 4
6 7
Входные данные
5
1 2 1 2 1
Выходные данные
2 5
3 4
1 4
1 4
Примечание

Обратите внимание, что не требуется минимизировать число совершённых операций. Достаточно, чтобы их было не больше 20 000.