K-cортування#2498

K-cортування

1 секунда

128 мегабайтів

Дуже легка

Сортування полягає в упорядкуванні заданого масиву чисел (або інших об'єктів) у зростаючому або спадному порядку. Існує багато варіацій цієї задачі, для яких існують дуже ефективні алгоритми. Важливим параметром цих алгоритмів є кількість перестановок, необхідних для сортування елементів масиву.

У цій задачі розглядаємо варіант, який називається $k$ -сортуванням. У $k$ -сортуванні ви можете виконати $k$ -перестановку, тобто обміняти значення двох елементів масиву, індекси яких відрізняються рівно на $k$ . Наприклад, розглянемо масив [ $6$ , $10$ , $4$ , $1$ , $2$ ] при $k = 3$ k = 3. Цей масив можна впорядкувати за зростанням за допомогою двох таких операцій: після першої перестановки масив стане [ $1$ , $10$ , $4$ , $6$ , $2$ ]; після другої перестановки — [ $1$ , $2$ , $4$ , $6$ , $10$ ].

Задано масив цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n. Ваше завдання — визначити мінімальну кількість $k$ -перестановок, необхідних для сортування цього масиву за неспаданням.

Вхідні дані

Перший рядок містить ціле число $n$ ( $1 \leq n \leq 300$ 1 \leq n \leq 300).

Другий рядок містить $n$ цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n ( $1 \leq a_{i} \leq 1 0^{9}$ 1 \leq a_i \leq 10^9 для всіх $i$ від $1$ до $n$ ).

Третій рядок містить ціле число $k$ ( $1 \leq k \leq n - 1$ 1 \leq k \leq n - 1).

Вихідні дані

Якщо масив можна впорядкувати за неспаданням за допомогою описаних операцій, виведіть мінімальну кількість $k$ -перестановок, необхідних для цього. Інакше виведіть $- 1$ .

Приклади

Приклад 1