Задана последовательность a[0]
, a[1]
, ... a[n-1]
из n чисел, каждый элемент уникален и принадлежит промежутку [0; n - 1]. Обменом назовем операцию (i, j) (0 ≤ i, j ≤ n - 1) которая меняет местами значения a[i]
и a[j]
. Отсортируйте последовательность при помощи наименьшего количества обменов. Вывести все проведенные обмены.
Первая строка содержит число n (n ≤ 10^6
). Вторая строка содержит n различных чисел из промежутка [0; n - 1].
В первой строке выведите наименьшее количество проведенных обменов k. В следующих k строках выведите все проведенные обмены в виде пар (i, j).