В этой задаче вам требуется отсортировать массив из n чисел, используя не более чем n обменов. Для заданного массива найдите последовательность попарных обменов элементов, после которых массив становится отсортированным по неубыванию. Обмены производятся последовательно, один за одним.
Обратите внимание, что в задаче не требуется минимизировать число обменов — требуется найти любой способ длины не более n.
Выходные данные
В первую строку выведите k (0 ≤ k ≤ n) — количество обменов. Следующие k строк должны содержать описания k искомых обменов по одному в строке. Каждый обмен выводится в виде пары целых чисел i, j (0 ≤ i, j ≤ n - 1), которая обозначает обмен элементов ai и aj. Индексы в парах можно выводить в любом порядке. Обмены производятся в порядке их вывода сверху вниз. Допускается вывод i = j и обмен пары элементов несколько раз.
Если ответов несколько, выведите любой из них. Гарантируется, что хотя бы один ответ существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5 2 5 1 4
|
2
0 3
4 2
|
|
2
|
6
10 20 20 40 60 60
|
0
|
|
3
|
2
101 100
|
1
0 1
|