Competitions

# Azerbaijan Programming Olympiad - 2nd Stage preparation

# Sorting Game

In The Sorting Game, you are given a sequence containing a permutation of the integers between **1** and **n**, inclusive. In one move, you can take any **k** consecutive elements of the sequence and reverse their order. Find the fewest number of moves to sort the sequence in ascending order.

#### Input

Consists of multiple test cases. The first line of each test case contains two integers **n** (**2** ≤ **n** ≤ **8**) and **k** (**2** ≤ **k** ≤ **n**). The second line of each test case contains a permutation of numbers from **1** to **n**.

#### Output

For each test case print in a separate line the fewest number of moves to sort the sequence in ascending order or **-1** if it's impossible.

Input example #1

3 3 1 2 3 3 3 3 2 1 8 4 7 2 1 6 8 4 3 5 5 4 3 2 4 1 5

Output example #1

0 1 7 -1