K-sorting#2498
Sorting involves arranging a given array of numbers (or other objects) in either ascending or descending order. There are many variations of this task, many of which have highly efficient algorithms. An important parameter of these algorithms is the number of swaps needed to sort the array elements.
In this problem, we consider a variant called -sorting. In -sorting, you can perform a -swap, which allows you to swap the values of two array elements whose indices differ by exactly . For example, consider the array [, , , , ] with k = 3. This array can be sorted in ascending order with two such operations: after the first swap, the array becomes [, , , , ]; after the second swap, it becomes [, , , , ].
Given an array of integers a_1, a_2, \ldots, a_n, your task is to determine the minimum number of -swaps required to sort this array in non-decreasing order.
The first line contains an integer (1 \leq n \leq 300).
The second line contains integers a_1, a_2, \ldots, a_n (1 \leq a_i \leq 10^9 for all from to ).
The third line contains an integer (1 \leq k \leq n - 1).
If the array can be sorted in non-decreasing order using the described operations, output the minimum number of -swaps needed. Otherwise, output .
Example 1