410173: GYM103967 I Побег из космической тюрьмы

I. Побег из космической тюрьмыограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

В этот раз Рик угодил в тюрьму вместе с Морти. Кажется, они пытались украсть какой-то очень важный кристалл... Но сейчас это уже не важно, нужно помочь им выбраться!

На дверях камеры написан массив $$$a$$$ из $$$n$$$ целых чисел. Числа в массиве могут повторяться, и известно, что двери тюрьмы открываются тогда и только тогда, когда массив будет отсортирован по неубыванию. Для изменения состояния массива используется специальный прибор, внутри которого спрятана $$$p$$$ — перестановка чисел от $$$1$$$ до $$$n$$$. После одного применения этого прибора, элементы массива меняют позиции в соответствии с этой перестановкой, то есть число $$$a_i$$$ перемещается на позицию $$$p_i$$$ для каждого $$$i$$$.

Закрывая дверь в камеру, охранник один раз применил этот прибор к исходному отсортированному массиву, после чего с ехидной улыбкой бросил этот прибор Рику — они оба знают, что чтобы вернуть массив в исходное состояние, в худшем случае Рику придется применить этот прибор еще $$$n! - 1$$$ раз. Но охранник не знал, что у Морти в кармане завалялась игрушка, способная запоминать и частично восстанавливать состояния объектов.

Рик и Морти составили план: каждую секунду Морти будет запоминать текущее состояние массива, после чего Рик будет применять к массиву перестановку $$$p$$$. Возможность выбраться у них появится тогда, когда для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ в игрушке Морти будет запомнено хотя бы одно состояние, в котором на $$$i$$$-й позиции стоит число, равное исходному значению $$$a_i$$$. Тогда Морти сможет по очереди восстановить каждое число в массиве из «правильного» состояния, после чего массив снова будет отсортирован по неубыванию.

Посчитайте, сколько секунд пройдет, прежде чем Рик и Морти смогут выбраться. Считайте, что Рик и Морти настолько сфокусированы на своем плане, что даже если первое применение перестановки $$$p$$$ оставит массив отсортированным, они этого не заметят и все равно потратят одну секунду на выполнение одного действия.

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

В первой строке дано единственное целое число $$$n$$$ — длина массива на двери и перестановки ($$$1 \leqslant n \leqslant 5 \cdot 10^5$$$).

Во второй строке через пробел перечислены $$$n$$$ целых чисел $$$a_i$$$ — изначальное (отсортированное) состояние массива $$$a$$$ ($$$1 \leqslant a_i \leqslant 10^9$$$; $$$a_i \leqslant a_{i+1}$$$).

В последней строке через пробел перечислены $$$n$$$ различных целых чисел $$$p_i$$$ — элементы перестановки, которую совершает одно использование прибора ($$$1 \leqslant p_i \leqslant n$$$).

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

Выведите единственное целое число — количество состояний массива, которое будет запомнено в игрушке Морти к моменту, когда заключенные впервые получат возможность с помощью нее выбраться из камеры.

ПримерыВходные данные

3
1 1 1
3 1 2

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

1

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

5
1 1 2 3 3
2 4 3 5 1

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

3

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

6
1 1 1 1 2 2
2 3 5 6 4 1

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

4

Примечание

В третьем примере состояния массива $$$a$$$ будут равны

1. $$$2, 1, 1, 2, 1, 1$$$
2. $$$1, 2, 1, 1, 1, 2$$$
3. $$$2, 1, 2, 1, 1, 1$$$
4. $$$1, 2, 1, 1, 2, 1$$$

Как можно заметить, $$$2$$$ не появляется на пятом месте до четвертой секунды, а на всех остальных позициях за эти четыре секунды хотя бы раз встретилось нужное число, поэтому ответ равен $$$4$$$.