G. Кольоровi книги

Сьогодні Козак Вус знайшов поличку книг. Усього на поличці було n книг, розташованих у ряд. На кожній книзі було написане одне ціле число a[i]. Усi цi числа рiзнi з проміжку [1; n]. Іншими словами, a — перестановка. Також кожна книга має свiй колiр, колiр i-ої книги c[i].

Козак хоче навести лад на поличці, для цього потрібно, щоб книги йшли в порядку зростання чисел, записаних на них, тобто книга 1 iде першою, наступна 2 i так далi. За одну операцію вiн може поміняти місцями будь-якi дві книги різного кольору. Допоможіть Вусу впоратись з цiєю задачею за мінімальну кількість операцій. Гарантується, що це можливо зробити.

Формат вхідних даних:

Перший рядок містить одне ціле число n (1 ≤ n ≤ 10^5) — кількість книг.

Другий рядок містить n цiлих чисел a[1]; a[2]; : : : ; a[n] (1 ≤ a[i] ≤ n) — числа, записанi на книгах.

Гарантується, що всi числа рiзнi.

Третiй рядок містить n цiлих чисел c[1]; c[2]; : : : ; c[n] (1 ≤ c[i] ≤ n) — кольори книг.

Гарантується, що рішення завжди iснує.

Формат вихідних даних:

У першому рядку виведіть одне число k — кількість операцій.

У наступних k рядках виведіть по два цiлi числа — позиції книг, якi потрібно поміняти місцями.

Оцінювання:

1. (до 50 балiв) n ≤ 1 000; припустимо, що m — мiнiмальна кiлькiсть операцiй, якi потрiбно зробити, щоб вiдсортувати книги в певному тестi, а k — кiлькiсть операцiй, якi ви використали.Тодi результат за цей тест буде рiвний:

50, якщо k = m

10 + ⌊30 - 30 * (k - m)/(3n - m)⌋, якщо m < k ⩽ 3n

0, якщо k > 3n.

Ваша кiлькiсть балiв за цей блок буде рiвною мiнiмуму з результатiв у всiх тестах з блоку.

1. (10 балiв) 1 000 < n ⩽ 10^5, усi кольори рiзнi.

2. (40 балiв) без додаткових обмежень.

Приклади