Codeforces Global Round 20 |
---|
Закончено |
У вас есть перестановка $$$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$$$.
3 3 2 1
1
1 1
0
10 1 8 4 3 7 10 6 5 9 2
1
В первом примере минимальное требуемое значение $$$s$$$ равно $$$1$$$.
Вот как мы можем преобразовать $$$p$$$ в пустую перестановку с $$$s=1$$$:
Можно показать, что при $$$s=0$$$ невозможно преобразовать $$$p$$$ в пустую перестановку.
Название |
---|