22189번 - K-cортировка 다국어

Задача сортировки состоит в упорядочивании заданного массива чисел (или других объектов) по возрастанию или убыванию. У этой задачи существует достаточно многих вариантов, для многих из которых существуют весьма эффективные алгоритмы. Одним из важных параметров этих алгоритмов является число обменов элементов массива, необходимых для упорядочивания.

Далее будем рассматривать вариант сортировки, который мы будем называть k-сортировкой. В этом варианте разрешается за одну операцию (называемую k-обменом) поменять местами значения двух элементов массива с номерами, отличающимися ровно на k. Например, если исходный массив имеет вид [6, 10, 4, 1, 2], а k = 3, то этот массив можно упорядочить по возрастанию за две операции (после первого обмена массив будет иметь вид [1, 10, 4, 6, 2], а после второго — [1, 2, 4, 6, 10]).

Задан массив целых чисел a₁, ..., a_n. Ваша задача состоит в том, чтобы определить минимальное число k-обменов, необходимое для упорядочивания этого массива по неубыванию.

Первая строка содержит целое число n (1 ≤ n ≤ 300). Вторая строка содержит n целых чисел a₁, ..., a_n (1 ≤ a_i ≤ 10⁹ для всех i от 1 до n). Третья строка содержит целое число k (1 ≤ k ≤ n - 1).

Если заданный массив можно упорядочить по неубыванию с использованием операций описанного типа, то выведите минимальное число k-обменов, необходимое для сортировки. Иначе, выведите одно число -1.