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

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
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))
		break
	return '\n'.join(map(str, rr))
print(main())


from heapq import heappush, heappop
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def solve():
	N = int(readline())
	INF = 10 ** 9
	A = tuple(map(int, readline().split()))
	B = tuple(range(1, N + 1))

	def check(N, A, N1):
		que = [(0, A)]
		dist = {A: 0}
		S = [A]
		B = list(A)
		for cost in range(N1):
			T = []
			for v in S:
				if dist[v] < cost:
					continue
				for i in range(N):
					B[:] = v
					for j in range(i + 1, N):
						B[i:j + 1] = reversed(v[i:j + 1])
						key = tuple(B)
						if cost + 1 < dist.get(key, N1 + 1):
							dist[key] = cost + 1
							T.append(key)
			S = T
		return dist
	D0 = check(N, A, (N - 1) // 2)
	D1 = check(N, B, (N - 1) // 2)
	ans = N - 1
	for (state, v) in D0.items():
		if state in D1:
			ans = min(ans, v + D1[state])
	write('%d\n' % ans)
solve()


from functools import lru_cache
import sys
from collections import deque
sys.setrecursionlimit(1000000)
sorted_a = ''
m = dict({})
N = int(input())
A = ''.join(list(map(lambda x: str(int(x) - 1), input().split())))
sorted_a = ''.join(list(sorted(A)))
q = deque()
q.append((A, 0))
m[A] = 0
while True:
	(a, x) = q.popleft()
	if a in m and m[a] < x:
		continue
	if x == (len(a) - 1) // 2:
		break
	for i in range(len(a)):
		for j in range(i + 2, len(a) + 1):
			next_a = a[:i] + a[::-1][len(a) - j:len(a) - i] + a[j:]
			if next_a in m:
				continue
			q.append((next_a, x + 1))
			m[next_a] = x + 1
m2 = dict({})
q = deque()
q.append((sorted_a, 0))
m2[sorted_a] = 0
while True:
	(a, x) = q.popleft()
	if a in m2 and m2[a] < x:
		continue
	if x == (len(a) - 1) // 2:
		break
	for i in range(len(a)):
		for j in range(i + 2, len(a) + 1):
			next_a = a[:i] + a[::-1][len(a) - j:len(a) - i] + a[j:]
			if next_a in m2:
				continue
			q.append((next_a, x + 1))
			m2[next_a] = x + 1
ret = sys.maxsize
for (a, x) in m.items():
	if a in m2:
		ret = min(ret, x + m2[a])
if ret == sys.maxsize:
	print(len(A) - 1)
else:
	print(ret)