Сьогоднi Козак Вус знайшов поличку книг. Усього на поличцi було n книг, розташованих у ряд. На кожнiй книзi було написане одне цiле число a[i]
. Усi цi числа рiзнi з промiжку [1; n]. Iншими словами, a — перестановка. Також кожна книга має свiй колiр, колiр i-ої книги c[i]
.
Козак хоче навести лад на поличцi, для цього потрiбно, щоб книги йшли в порядку зростання чисел, записаних на них, тобто книга 1 iде першою, наступна 2 i так далi. За одну операцiю вiн може помiняти мiсцями будь-якi двi книги рiзного кольору. Допоможiть Вусу впоратись з цiєю задачею за мiнiмальну кiлькiсть операцiй. Гарантується, що це можливо зробити.
Перший рядок мiстить одне цiле число n (1 ⩽ n ⩽ 10^5
) — кiлькiсть книг.
Другий рядок мiстить n цiлих чисел a[1]
; a[2]
; : : : ; a[n]
(1 ⩽ a[i]
⩽ n) — числа, записанi на книгах.
Гарантується, що всi числа рiзнi.
Третiй рядок мiстить n цiлих чисел c[1]
; c[2]
; : : : ; c[n]
(1 ⩽ c[i]
⩽ n) — кольори книг.
Гарантується, що рiшення завжди iснує.
У першому рядку виведiть одне число k — кiлькiсть операцiй.
У наступних k рядках виведiть по два цiлi числа — позицiї книг, якi потрiбно помiняти мiсцями.
####Оцiнювання
(до 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х тестах з блоку.
(10 балiв) 1 000 < n ⩽ 10^5
, усi кольори рiзнi.
(40 балiв) без додаткових обмежень.