Автор задачи и разработчик: Даниил Орешников
Воспользуемся стандартной идеей разбиения перенстановки на циклы. Рассмотрим произвольный индекс $$$i$$$, а затем посмотрим на $$$p[i]$$$, $$$p[p[i]]$$$, и так далее. Рано или поздно этот ряд зациклится, образуя цикл, по которому элементы переставляются при применении данной перестановки.
Рассмотрим все элементы исходного массива и соответствующие им циклы. Заметим, что впервые каждый элемент окажется «на своем месте» (что позволит его затем использовать с помощью запоминающего устройства) через столько шагов, через сколько на цикле расположено равное ему число.
Таким образом, мы свели задачу к тому, чтобы для каждого числа найти ближайшее равное ему на его цикле. В частности, на цикле, на котором число встречается только один раз, его следующее появление будет только на шаге, равном длине цикла. Чтобы в общем случае для каждой позиции найти следующее появление равного числа, заведем HashMap (unordered_set), в котором будем хранить последнее вхождение каждого числа, и проитерируемся по удвоенному циклу, обновляя актуальную информацию.
Когда мы для каждого элемента нашли ближайшее вхождение равного ему в цикл, останется только взять максимум из всех полученных величин, что и будет ответом. Время работы этого решения равно $$$\mathcal{O}(n)$$$.