E. Сортировка инверсиями
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Madeline есть массив $$$a$$$ состоящий из $$$n$$$ целых чисел. Пара $$$(u, v)$$$ образует инверсию в массиве $$$a$$$ если

  • $$$1 \le u < v \le n$$$.
  • $$$a_u > a_v$$$.

Madeline только что обнаружила магический листочек, который позволяет ей написать два индекса $$$u$$$ и $$$v$$$ и поменять местами значения $$$a_u$$$ и $$$a_v$$$. Будучи скучающим, она решила написать список пар $$$(u_i, v_i)$$$ со следующими условиями:

  • Все пары в списке различны и каждая из них является инверсией в массиве $$$a$$$.
  • Все пары которые образуют инверсию в массиве $$$a$$$ присутствуют в списке.
  • Начиная с данного массива, если поменять местами числа стоящие в позициях $$$u_1$$$ и $$$v_1$$$, потом числа стоящие в позициях $$$u_2$$$ и $$$v_2$$$, и так далее, то после всех этих операций массив $$$a$$$ будет отсортирован в порядке неубывания.
Создайте такой список или скажите что сделать это невозможно. Если есть несколько решений, вы можете найти любое из них.
Входные данные

Первая строка ввода содержит одно целое число $$$n$$$ ($$$1 \le n \le 1000$$$) — длину массива.

Следующая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,...,a_n$$$ $$$(1 \le a_i \le 10^9)$$$  — элементы массива.

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

Выведите -1 если нет подходящего списка. В противном случае выведите $$$m$$$ ($$$0 \le m \le \dfrac{n(n-1)}{2}$$$) — количество пар в списке.

$$$i$$$-я из следующих $$$m$$$ строк должна состоять из двух целых чисел $$$u_i, v_i$$$ ($$$1 \le u_i < v_i\le n$$$).

Если есть несколько решений, вы можете найти любое из них.

Примеры
Входные данные
3
3 1 2
Выходные данные
2
1 3
1 2
Входные данные
4
1 8 1 6
Выходные данные
2
2 4
2 3
Входные данные
5
1 1 1 2 2
Выходные данные
0
Примечание

В первом примере массив будет изменен следующим образом $$$[3,1,2] \rightarrow [2,1,3] \rightarrow [1,2,3]$$$.

Во втором примере $$$[1,8,1,6] \rightarrow [1,6,1,8] \rightarrow [1,1,6,8]$$$.

В третем примере массив уже отсортирован.