Всі полюбляють перестановки

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

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

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

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

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