Fixed-Length Reversal Sort

Interview

Time limit2sMemory limit128 MB

Summary

Given a permutation of up to 8 numbers, find the minimum number of fixed-length K reversals needed to sort it, or report impossibility.

Level: Medium5 of 10
Topics: BFS, Graph, Array, Brute force
Solved: No attempts yet

Problem

You are given a permutation of length N containing each integer from 1 through N exactly once.

In one move, choose a starting position and reverse exactly K consecutive numbers from that position to the right. The chosen position must allow all K numbers to stay inside the permutation. For example, if the permutation is 5 4 3 2 1 and K is 3, reversing from the second position changes it to 5 2 3 4 1.

Find the minimum number of moves needed to make the given permutation increasing. If it cannot be done, output -1.

Input

The first line contains N and K. The second line contains the N numbers of the permutation.

Output

Print the minimum number of moves. If the permutation cannot be made increasing, print -1.

Constraints

2 ≤ K ≤ N ≤ 8

Examples5

Example 1
Input
```
3 3
3 2 1
```
Expected output
```
1
```
Example 2
Input
```
3 3
1 2 3
```
Expected output
```
0
```
Example 3
Input
```
5 2
5 4 3 2 1
```
Expected output
```
10
```
Example 4
Input
```
5 4
3 2 4 1 5
```
Expected output
```
-1
```
Example 5
Input
```
8 4
7 2 1 6 8 4 3 5
```
Expected output
```
7
```