Кожну перестановку можна розбити на "цикли".

Позначимо $p^k(i) = p[p^{k-1}(i)]$, і $p^0(i) = i$. Будемо перебирати $k$ за зростанням з $1$. Колись ми зациклимось, тому що прийдемо в якийсь елемент, де вже були.

\begin{enumerate}
\item Чому це колись станеться? Якби ми не знайшли такий цикл, то це означало що в нас є нескінченно багато елементів в перестановці.
\item Чому це буде саме цикл? Якби це був не цикл, то для якогось числа $x$ його число входжень у перестановку було більше за $1$.
\end{enumerate}

Ми розбили перестановку на цикли. Тепер треба порахувати суму індексів. Розвернемо цикл в іншу сторону, щоб йти так, як нам сказано в задачі. Тоді, нам залишається тільки зробити префіксні суми на цих циклах і акуратно підрахувати відповідь --- порахувати скільки разів цикл повність пройдеться, і скільки ще елементів після повного проходу воно обійде.

Асимптотика --- $\mathcal{O}(N)$