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

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

На дверях камеры написан массив $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$).

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

В третьем примере состояния массива $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$.