Задача H. Марфа Геннадьевна и документы ≡

Условие

У Марфы Геннадьевны есть папка с файлами (не компьютерная, а обычная), в которую она складывает свои документы. Марфа Геннадьевна пронумеровала свои документы от 1 до N и уже привыкла к тому, что у неё в первом файле лежит первый документ, во втором файле — второй и т.д.

Однажды к Марфе Геннадьевне пришёл в гости внук и стал рассматривать её документы. Разумеется, после этого документы оказались не на своих местах.

Теперь Марфа Геннадьевна хочет переложить документы в правильном порядке так, чтобы минимизировать количество выкладываний и вкладываний документов. Также требуется, чтобы при перекладываниях каждый раз вне папки находилось не более двух документов (чтобы не потерять документы).

Напишите программу, принимающую на вход расположение документов после визита внука, и выводящую искомую последовательность выкладываний и вкладываний документов.

Формат входного файла

Входной файл содержит целое число N, за которым следуют N целых чисел a_i, где число a_i означает, что в i-м файле лежит документ с номером a_i.

Формат выходного файла

Выходной файл должен содержать целое число K — количество выкладываний и вкладываний документов.

Далее должны следовать K пар целых чисел. Пара  − j i означает выкладывание документа с номером j, находящегося в i-м файле. Пара j i означает вкладывание документа с номером j в i-й файл. Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N ≤ 10⁵, 1 ≤ a_i ≤ N. Все числа a_i различны.

Примеры тестов

3
1 3 2

4
-3 2
-2 3
3 3
2 2

4
1 4 2 3

6
-4 2
-3 4
4 4
-2 3
3 3
2 2

3
1 2 3

0

Разбор

Очевидно, что минимальное количество действий равно количеству документов, которые лежат не на своих местах, умноженному на 2.

Начнем с любого i, для которого a_i ≠ i, и обойдем соответствующий цикл перестановки. Сначала вынем документ с номером k = a_i, находящийся в i-м файле. Положим a_i = 0.

Предположение индукции: документ с номером k вынут. Затем повторим следующие действия, пока a_k ≠ 0. Вынем документ с номером a_k, находящийся в k-м файле, и положим в k-й файл документ с номером k, который мы ранее вынули из другого файла. Далее положим k = a_k.

Описанные действия нужно проделать для каждого цикла перестановки, то есть начиная со всех i, для которых a_i ≠ i.

const
  MAX_N = 100000;
var
  a: array[1..MAX_N] of integer;
  n, cnt, i, k, tmp: integer;
begin
  assign(input, 'input.txt');
  reset(input);
  assign(output, 'output.txt');
  rewrite(output);

  read(n);
  for i := 1 to n do
    read(a[i]);

  cnt := 0;
  for i := 1 to n do
  begin
    if (a[i] <> i) then
      inc(cnt);
  end;
  writeln(2*cnt);

  for i := 1 to n do
  begin
    if (a[i] <> i) then
    begin
      k := a[i];
      a[i] := 0;
      writeln(-k, ' ', i);
      while (a[k] <> 0) do
      begin
        writeln(-a[k], ' ', k);
        writeln(k, ' ', k);
        tmp := a[k];
        a[k] := k;
        k := tmp;
      end;
      writeln(k, ' ', k);
    end;
  end;

  close(input);
  close(output);
end.