| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 1 | 1 | 1 | 100.000% |
В этот раз Рик угодил в тюрьму вместе с Морти. Кажется, они пытались украсть какой-то очень важный кристалл... Но сейчас это уже не важно, нужно помочь им выбраться!
На дверях камеры написан массив $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$ будут равны
Как можно заметить, 2ドル$ не появляется на пятом месте до четвертой секунды, а на всех остальных позициях за эти четыре секунды хотя бы раз встретилось нужное число, поэтому ответ равен 4ドル$.