E. Антон и Ира
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Антон любит получать из одной перестановки другую переставляя её элементы местами за деньги, а Ира не любит платить за глупые игры. Помогите им получить нужную перестановку, заплатив за это как можно меньше.

Более формально, у нас есть две перестановки p и s чисел от 1 до n. Мы можем поменять местами pi и pj, заплатив за это |i - j| монет. Найдите и выведите наименьшее количество монет,которое потребуется, чтобы получить из перестановки p перестановку s. Так же выведите последовательность операций обмена элементов, при которой достигается ответ.

Входные данные

В первой строке записано одно число n (1 ≤ n ≤ 2000) — длина перестановок.

Во второй строке записана последовательность из n чисел от 1 до n — перестановка p. Каждое число от 1 до n встречается по разу в этой строке.

В третьей строке записана последовательность из n чисел от 1 до n — перестановка s. Каждое число от 1 до n встречается по разу в этой строке.

Выходные данные

В первой строке выведите минимальное количество монет, которое нужно потратить для получения перестановки s из перестановки p.

Во второй строке выведите число k (0 ≤ k ≤ 2·106) - число операций для достижения ответа.

В следующих k строках выведите сами операции. Каждая строка должна содержать два числа i и j (1 ≤ i, j ≤ n, i ≠ j), что означает, что надо поменять местами pi и pj.

Гарантируется, что ответ существует.

Примеры
Входные данные
4
4 2 1 3
3 2 4 1
Выходные данные
3
2
4 3
3 1
Примечание

В первом тесте из условия первым ходом мы поменяем местами числа на позициях 3 и 4, и перестановка p примет вид 4 2 3 1. За это мы заплатим |3 - 4| = 1 монету. Вторым ходом поменяем местами числа на позициях 1 и 3, и получим перестановку 3241, которая равна s. За этот ход мы платим |3 - 1| = 2 монеты. Суммарно мы заплатим 3 монеты.