Given a permutation of {1, …, n}, you must sort it in increasing order. The only operation allowed is to reverse the first i elements of the current permutation, for any 2 ≤ i ≤ n.

For instance, in one step we can transform [3, 5, 2, 4, 1] into [5, 3, 2, 4, 1], [2, 5, 3, 4, 1], [4, 2, 5, 3, 1] and [1, 4, 2, 5, 3].

Given a permutation, what is the minimum number of steps to sort it?

Input

Input consists of several permutations, each with an n between 1 and 18, followed by n different numbers between 1 and n.

Output

For every permutation, print the minimum number of operations to sort it.

Public test cases

**Input**

3 1 2 3 2 2 1 1 1 4 2 1 4 3 6 1 3 2 6 5 4 8 4 1 7 8 3 6 5 2 18 11 17 3 10 14 1 18 5 9 6 13 15 4 8 2 12 16 7

**Output**

0 1 0 3 5 7 19

Information

- Author
- Josep Grané
- Language
- English
- Official solutions
- C++
- User solutions
- C++