K-cортування
Зада часортування полягає в упорядкуванні заданого масиву чисел (або інших об'єктів) за зростанням або спаданням. У цієї задачі існує досить багато варіантів, у багатьох із яких є дуже ефективні алгоритми. Одним із важливих параметрів цих алгоритмів є кількість обмінів елементів масиву, необхідні для впорядкування.
Далі будемо розглядати варіант сортування, який ми називатимемо -сортування. У цьому варіанті дозволяється за одну операцію (звану -обміном) поміняти місцями значення двох елементів масиву з номерами, що відрізняються рівно на . Наприклад, якщо вихідний масив має вигляд [, , , , ], а = , то цей масив можна впорядкувати за зростанням за дві операції (після першого обміну масив матиме вигляд [, , , , ], а після другого - [, , , , ].
Задано масив цілих чисел , ..., . Ваше завдання полягає в тому, щоб визначити мінімальну кількість -обмінів, необхідну для впорядкування цього масиву за неспаданням.
Вхідні дані
Перший рядок містить ціле число ( ≤ ≤ ). Другий рядок містить цілих чисел , ..., ( ≤ ≤ для всіх від до ). Третій рядок містить ціле число ( ≤ ≤ - ).
Вихідні дані
Якщо заданий масив можна впорядкувати за неспаданням з використанням операцій описаного типу, виведіть мінімальне число -обмінів, необхідні для сортування. Інакше виведіть одне число .