Sorting a permutation P77983

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.