410173: GYM103967 I Побег из космической тюрьмы
Description
В этот раз Рик угодил в тюрьму вместе с Морти. Кажется, они пытались украсть какой-то очень важный кристалл... Но сейчас это уже не важно, нужно помочь им выбраться!
На дверях камеры написан массив $$$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, 1, 1, 2, 1, 1$$$
- $$$1, 2, 1, 1, 1, 2$$$
- $$$2, 1, 2, 1, 1, 1$$$
- $$$1, 2, 1, 1, 2, 1$$$
Как можно заметить, $$$2$$$ не появляется на пятом месте до четвертой секунды, а на всех остальных позициях за эти четыре секунды хотя бы раз встретилось нужное число, поэтому ответ равен $$$4$$$.