Задачи
Сортировка от 0 до n - 1
Сортировка от 0 до n - 1
Задана последовательность a0
, a1
, ... an-1
из n чисел, каждый элемент уникален и принадлежит промежутку [0; n - 1]. Обменом назовем операцию (i, j) (0 ≤ i, j ≤ n - 1) которая меняет местами значения ai
и aj
. Отсортируйте последовательность при помощи наименьшего количества обменов. Вывести все проведенные обмены.
Входные данные
Первая строка содержит число n (n ≤ 106
). Вторая строка содержит n различных чисел из промежутка [0; n - 1].
Выходные данные
В первой строке выведите наименьшее количество проведенных обменов k. В следующих k строках выведите все проведенные обмены в виде пар (i, j).
Входные данные #1
3 0 2 1
Выходные данные #1
1 1 2
Входные данные #2
5 4 0 3 2 1
Выходные данные #2
3 1 4 3 2 4 0