k-sorting

Interview

Time limit2sMemory limit256 MB

Summary

Given an array and a fixed step k, find the minimum number of swaps of elements exactly k positions apart needed to sort the array in nondecreasing order, or -1 if impossible.

Level: Medium5 of 10
Topics: Sorting, Greedy, Array, Math
Solved: No attempts yet

Problem

A sorting problem asks you to arrange a given array of numbers (or other objects) in increasing or decreasing order. There are many variants of this problem, and efficient algorithms exist for quite a few of them. One important parameter of these algorithms is the number of element swaps needed to order the array.

Below we consider a sorting variant we will call k-sorting. In this variant, one operation (called a k-swap) allows you to exchange the values of two elements whose indices differ by exactly k. For example, if the initial array is [6, 10, 4, 1, 2] and k = 3, the array can be sorted in increasing order in two operations: after the first swap the array becomes [1, 10, 4, 6, 2], and after the second it becomes [1, 2, 4, 6, 10].

You are given an integer array a1, ..., an. Your task is to determine the minimum number of k-swaps needed to sort this array in nondecreasing order.

Input

The first line contains an integer n (1 ≤ n ≤ 300). The second line contains n integers a1, ..., an (1 ≤ ai ≤ 109 for all i from 1 to n). The third line contains an integer k (1 ≤ k ≤ n - 1).

Output

If the given array can be sorted in nondecreasing order using operations of the described type, output the minimum number of k-swaps needed to sort it. Otherwise, output a single number -1.

Examples1

Example 1
Input
```
5
6 10 4 1 2
3
```
Expected output
```
2
```