Антон любит получать из одной перестановки другую переставляя её элементы местами за деньги, а Ира не любит платить за глупые игры. Помогите им получить нужную перестановку, заплатив за это как можно меньше.
Более формально, у нас есть две перестановки p и s чисел от 1 до n. Мы можем поменять местами pi и pj, заплатив за это |i - j| монет. Найдите и выведите наименьшее количество монет,которое потребуется, чтобы получить из перестановки p перестановку s. Так же выведите последовательность операций обмена элементов, при которой достигается ответ.
Выходные данные
В первой строке выведите минимальное количество монет, которое нужно потратить для получения перестановки s из перестановки p.
Во второй строке выведите число k (0 ≤ k ≤ 2·106) - число операций для достижения ответа.
В следующих k строках выведите сами операции. Каждая строка должна содержать два числа i и j (1 ≤ i, j ≤ n, i ≠ j), что означает, что надо поменять местами pi и pj.
Гарантируется, что ответ существует.
Примечание
В первом тесте из условия первым ходом мы поменяем местами числа на позициях 3 и 4, и перестановка p примет вид 4 2 3 1. За это мы заплатим |3 - 4| = 1 монету. Вторым ходом поменяем местами числа на позициях 1 и 3, и получим перестановку 3241, которая равна s. За этот ход мы платим |3 - 1| = 2 монеты. Суммарно мы заплатим 3 монеты.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4 2 1 3
3 2 4 1
|
3
2
4 3
3 1
|