Problem: A permutation of N numbers from 1 to N A1, A2, ……, AN is given. You can perform the operation reverse (i, j) to reverse the order of the numbers in the interval [i, j] (1 ≤ i ≤ j ≤ N) for this permutation. For example, if reverse (2, 4) is applied to [1, 2, 3, 4, 5], it becomes [1, 4, 3, 2, 5]. Calculate how many operations you need to do at a minimum to get the permutation sorted in ascending order.

Constraints

* N is an integer

* 2 ≤ N ≤ 10

Input

The input is given in the following format.

> N
> A1 A2 …… AN
>

Output

Print the solution to the problem on one line.

Examples

Input

5
1 4 3 5 2


Output

2


Input

5
3 1 5 2 4


Output

4


Input

3
1 2 3


Output

0


Input

10
3 1 5 2 7 4 9 6 10 8


Output

9

Solution (in PYTHON3):

Solution:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f(n):
        a = LI()

        def search(s,t):
            n2 = 4
            d = collections.defaultdict(lambda: inf)
            d[s] = 0
            q = []
            heapq.heappush(q, (0, s))
            v = collections.defaultdict(bool)
            while len(q):
                k, u = heapq.heappop(q)
                if v[u]:
                    continue
                v[u] = True
                if u == t:
                    return k

                vd = k + 1
                for i in range(n):
                    for j in range(i+1,n):
                        uv = tuple(u[:i] + u[i:j+1][::-1] + u[j+1:])
                        if v[uv]:
                            continue
                        if d[uv] > vd:
                            d[uv] = vd
                            if vd < 4:
                                heapq.heappush(q, (vd, uv))

            return d

        r1 = search(tuple(a), tuple(range(1,n+1)))
        if isinstance(r1, int):
            return r1
        r2 = search(tuple(range(1,n+1)), tuple(a))
        r = n - 1
        for k,v in r1.items():
            t = v + r2[k]
            if r > t:
                r = t

        return r


    while 1:
        n = I()
        if n == 0:
            break
        rr.append(f(n))
        # print('rr', rr[-1])
        break

    return '\n'.join(map(str,rr))


print(main())