Given a permutation of 1 to n, you need to perform some operations to make it into increasing order. Each operation is to reverse an interval \(a_1,a_2,\dots,a_x(1\le x\le n)\) (a prefix). Your goal is to minimize the number of operations.

Input

The first line contains an integer \(n\) (\(1\le n\le 8\)).

The second line contains \(n\) space separated integers, representing the sequence \(a\).

Output

An integer representing the answer, that is, the minimum number of operations needed to make the permutation into increasing order.