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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
#define D10 fixed<<setprecision(10)
typedef long long ll;
typedef long double ld;
typedef vector<short> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

int n;

map<vi, short> bfs(vi v)
{
	map<vi, short> mp;
	queue<vi> que;
	que.push(v); mp[v] = 0;
	while (que.size())
	{
		vi tmp = que.front();
		que.pop();
		int t = mp[tmp];
		if (t >= (n-1) / 2) continue;
		REP(i, n)REP(j, i)
		{
			vi nx = tmp;
			reverse(nx.begin() + j, nx.begin() + i + 1);
			if (mp.find(nx) != mp.end()) continue;
			else
			{
				mp[nx] = t + 1;
				que.push(nx);
			}
		}
	}
	return mp;
}

signed main()
{
	cin >> n;
	vi a(n), b;
	REP(i, n) cin >> a[i];
	b = a;
	sort(ALL(b));
	auto mp1 = bfs(a);
	auto mp2 = bfs(b);
	int ans = n - 1;
	for (auto it = mp1.begin(); it != mp1.end(); it++)
	{
		if (mp2.find(it->first) != mp2.end()) chmin(ans, it->second + mp2[it->first]);
	}
	cout << ans << endl;
	return 0;
}