У 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\) будет отсортирован в порядке неубывания.
Создайте такой список или скажите что сделать это невозможно. Если есть несколько решений, вы можете найти любое из них.
Выходные данные
Выведите -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,1,2] \rightarrow [2,1,3] \rightarrow [1,2,3]\).
Во втором примере \([1,8,1,6] \rightarrow [1,6,1,8] \rightarrow [1,1,6,8]\).
В третем примере массив уже отсортирован.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 1 2
|
2
1 3
1 2
|
|
2
|
4
1 8 1 6
|
2
2 4
2 3
|
|
3
|
5
1 1 1 2 2
|
0
|