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.