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<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
short n; vector<short>a; queue<pair<vector<short>,short>>Q;
vector<pair<vector<short>, short>>a1, a2;
set<vector<short>>E;
void init(vector<short>R, short Lim, short D) {
	Q.push(make_pair(R, 0)); E.clear(); E.insert(R);
	while (!Q.empty()) {
		vector<short>H = Q.front().first; short L = Q.front().second; Q.pop();
		if (D == 0)a1.push_back(make_pair(H, L));
		if (D == 1)a2.push_back(make_pair(H, L));
		if (L == Lim)continue;
		for (short i = 0; i < n; i++) {
			for (short j = i + 1; j < n; j++) {
				vector<short>I = H; short Y = j;
				for (short k = i; k <= (i + j) / 2; k++) {
					swap(I[k], I[Y]); Y--;
				}
				if (E.find(I) == E.end()) {
					Q.push(make_pair(I, L + 1));
					E.insert(I);
				}
			}
		}
	}
}
int main() {
	cin >> n; for (short i = 0; i < n; i++) { short p; cin >> p; a.push_back(p); }
	short pos = min(4, n / 2); short pos2 = (n - 1) / 2; init(a, pos, 0); vector<short>Zero;
	for (int i = 0; i < n; i++)Zero.push_back(i + 1); init(Zero, pos2, 1);
	sort(a2.begin(), a2.end());
	short ret = n - 1;
	for (short i = 0; i < a1.size(); i++) {
		int S1 = lower_bound(a2.begin(), a2.end(), make_pair(a1[i].first, (short)0)) - a2.begin();
		int S2 = upper_bound(a2.begin(), a2.end(), make_pair(a1[i].first, pos)) - a2.begin();
		if (S1 != S2)ret = min(ret, (short)(a1[i].second + a2[S1].second));
	}
	cout << ret << endl;
	return 0;
}