Даны две перестановки \(p_1,p_2,\ldots,p_n\) и \(q_1,q_2,\ldots,q_n\) длины \(n\). За одну операцию вы можете выбрать два целых числа \(1\leq i,j\leq n,i\neq j\) и поменять местами \(p_i\) и \(p_j\). Стоимость операции равна \(\min (|i-j|,|p_i-p_j|)\).
Найдите минимальную стоимость последовательности операций, в результате которых для всех \(1\leq i\leq n\) выполняется равенство \(p_i = q_i\), и выведите последовательность с минимальной стоимостью.
Перестановкой длины \(n\) является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
Выходные данные
Для каждого набора входных данных выведите общее количество операций \(k\) (\(0\le k\le n^2\)) в первой строке. Затем выведите \(k\) строк, каждая из которых содержит два целых числа \(i,j\) (\(1\le i,j\le n\), \(i\neq j\)) — операцию обмена \(p_i\) и \(p_j\). Операции выводите в порядке выполнения.
Можно показать, что ни одна оптимальная последовательность операций не имеет длину больше \(n^2\).
Примечание
Во втором наборе входных данных вы можете поменять местами \(p_1,p_3\), что будет стоить \(\min(|1-3|,|1-3|)=2\). Тогда \(p\) станет равно \(q\), а общая стоимость равна \(2\).
В третьем наборе входных данных вы можете выполнить следующие операции:
Изначально, \(p=[2,1,4,3]\).
- Поменять местами \(p_1,p_4\), что будет стоить \(\min(|1-4|,|2-3|)=1\), в результате чего \(p=[3,1,4,2]\).
- Поменять местами \(p_2,p_4\), что будет стоить \(\min(|2-4|,|1-2|)=1\), в результате чего \(p=[3,2,4,1]\).
- Поменять местами \(p_1,p_3\), что будет стоить \(\min(|1-3|,|3-4|)=1\). Тогда \(p\) станет равно \(q\). Общая стоимость равна \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2
2 1
2 1
3
1 2 3
3 2 1
4
2 1 4 3
4 2 3 1
5
1 4 3 2 5
5 2 3 4 1
|
0
1
1 3
3
1 4
2 4
1 3
4
1 2
4 5
2 5
1 4
|