Кожну перестановку можна розбити на "цикли".
Позначимо $$$p^k(i) = p[p^{k-1}(i)]$$$, і $$$p^0(i) = i$$$. Будемо перебирати $$$k$$$ за зростанням з $$$1$$$. Колись ми зациклимось, тому що прийдемо в якийсь елемент, де вже були.
Ми розбили перестановку на цикли. Тепер треба порахувати суму індексів. Розвернемо цикл в іншу сторону, щоб йти так, як нам сказано в задачі. Тоді, нам залишається тільки зробити префіксні суми на цих циклах і акуратно підрахувати відповідь — порахувати скільки разів цикл повність пройдеться, і скільки ще елементів після повного проходу воно обійде.
Асимптотика — $$$\mathcal{O}(N)$$$