У вас есть перестановка \(p\) целых чисел от \(1\) до \(n\).
У вас есть сила \(s\) и вы будете выполнять следующую операцию несколько раз:
Можно показать, что независимо от того, какое число \(i\) вы выбрали, после всех операций \(p\) будет перестановкой целых чисел от \(1\) до \(|p|\).
Вы хотите превратить \(p\) в пустую перестановку. Найдите минимальную силу \(s\), которая позволит вам это сделать.
Первая строка ввода содержит одно целое число \(n\) (\(1 \leq n \leq 5 \cdot 10^5\)) — длину перестановки \(p\).
Вторая строка ввода содержит \(n\) целых чисел \(p_1, p_2, \ldots, p_n\) (\(1 \leq p_i \leq n\)) — элементы перестановки \(p\).
Гарантируется, что все элементы в \(p\) различны.
Выведите минимальную необходимую силу \(s\).
В первом примере минимальное требуемое значение \(s\) равно \(1\).
Вот как мы можем преобразовать \(p\) в пустую перестановку с \(s=1\):
Можно показать, что при \(s=0\) невозможно преобразовать \(p\) в пустую перестановку.
3 3 2 1
1
1 1
0
10 1 8 4 3 7 10 6 5 9 2
5000 ms 1024 Mb Правила оформления программ и список ошибок при автоматической проверке задач