Розбір
Кожну перестановку можна розбити на "цикли".
Позначимо , і . Будемо перебирати за зростанням з . Колись ми зациклимось, тому що прийдемо в якийсь елемент, де вже були.
Чому це колись станеться? Якби ми не знайшли такий цикл, то це означало що в нас є нескінченно багато елементів в перестановці.
Чому це буде саме цикл? Якби це був не цикл, то для якогось числа його число входжень у перестановку було більше за .
Ми розбили перестановку на цикли. Тепер треба порахувати суму індексів. Розвернемо цикл в іншу сторону, щоб йти так, як нам сказано в задачі. Тоді, нам залишається тільки зробити префіксні суми на цих циклах і акуратно підрахувати відповідь — порахувати скільки разів цикл повність пройдеться, і скільки ще елементів після повного проходу воно обійде.
Асимптотика —