← К соревнованиям

Sort Me Round

Подарок для Сорт-Ми-Тян

Сложность: 64%

Вы решили подарить Сорт-Ми-Тян массив aa длиной nn, в котором могут встречаться числа от 11 до 512512.

Вы уже купили массив, как вдруг КФ-Тян – подружка Сорт-Ми-Тян, которая тайно в вас влюблена и поэтому помогает – рассказала, что ей удалось выяснить, что Сорт-Ми-Тян хочет на новый год. Оказалось, вы почти угадали: она хочет массив bb длиной nn, в котором могут встречаться числа от 11 до 512512, но только вот само содержание массива другое.

К сожалению, в магазине массив aa отказались менять на другой, но согласились починить в сервисе. Починка заключается в том, что вы даёте мастеру перестановку pp чисел от 11 до 512512, а он меняет значения массива по правилу a[i]=p[a[i]]a[i] = p[a[i]] (индексация с единицы).

Определить, насколько подарок удался, можно так: очки радости, которые Сорт-Ми-Тян получит от вашего подарка, равны количеству таких ii, что a[i]=b[i]a[i] = b[i]. Конечно, вы хотите максимизировать этот показатель.

Выведите максимально возможное количество очков радости Сорт-Ми-Тян после получения вашего подарка, если перед этим вы почините его у мастера.

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

В первой строке записано число nn – длина массивов.

В следующей строке записано nn чисел - это массив aa, который вы купили.

В следующей строке записано ещё nn чисел - это массив bb, который хочет Сорт-Ми-Тян.

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

Выведите одно число – максимально возможное количество очков радости Сорт-Ми-Тян после получения вашего подарка, если перед этим вы почините его у мастера.

Подзадачи

баллынеобх. подзадачиограничения
1

10

-

n8n \le 8

2

10

1

n20n \le 20

3

20

2

n100n \le 100

4

30

3

n3000n \le 3000

5

30

4

n105n \le 10^5

STDINSTDOUT
3
1 2 3
3 1 2
3
4
1 3 3 5
1 1 5 5
2

Примечание

В первом примере лучший результат даёт любая перестановка pp, начинающаяся с [3,1,2][3, 1, 2].

Во втором – любая, начинающаяся на [1,?,?,?,5][1, ?, ?, ?, 5], [?,?,1,?,5][?, ?, 1, ?, 5] или [1,?,3,?,?][1, ?, 3, ?, ?], где ?? – любое число.