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 "climits"
#include "list"
#include "queue"
#include "vector"
#include "string"
#include "map"
#include "unordered_map"
#include "algorithm"

using namespace std;

const long long int MOD = 1000000007;

long long int N, M, K, H, W, L, R;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;
	int cnt = 0;
	long long int gl = 0;
	vector<long long int>v(N);
	for (int i = 0; i < N; i++) {
		v[i] = i + 1;
		gl += v[i] << (i<<2);
	}
	for (int i = 0; i < N; i++)cin >> v[i];
	unordered_map<long long int,int>dis;
	long long int bag = 0;
	for (int i = 0; i < N; i++) {
		bag += (v[i] << (i<<2));
	}
	dis[bag] = 0;
	queue<long long int>Q;
	Q.push(bag);
	while (!Q.empty()) {
		long long int cn = Q.front();
		if (dis[cn] == 5)break;
	//	cout << cn << endl;
		Q.pop();
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				long long int cc = cn;
				for (int k = i; k < (i + j + 1) / 2; k++) {
					long long int a = (cc >> (k<<2)) & ((1 << 4)-1);
					long long int b = (cc >> ((i + j - k)<<2)) & ((1 << 4)-1);
		//			cout << i << " " << j << " " << a << " " << b << endl;
					cc += (b - a) << (k<<2);
					cc += (a - b) << ((i + j - k)<<2);
				}
				if (dis.find(cc) == dis.end()) {
					dis[cc] = dis[cn] + 1;
					Q.push(cc);
				}
				else if (dis[cc] > dis[cn] + 1) {
					dis[cc] = dis[cn] + 1;
					Q.push(cc);
				}
			}
		}
	}
	queue<long long int>QQ;
	unordered_map<long long int, int>ddis;
	ddis[gl] = 0;
	QQ.push(gl);
	while (!QQ.empty()) {
		long long int cn = QQ.front();
		if (ddis[cn] == 4)break;
	//		cout << cn << endl;
		QQ.pop();
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				long long int cc = cn;
				for (int k = i; k < (i + j + 1) / 2; k++) {
					long long int a = (cc >> (k << 2)) & ((1 << 4) - 1);
					long long int b = (cc >> ((i + j - k) << 2)) & ((1 << 4) - 1);
					//			cout << i << " " << j << " " << a << " " << b << endl;
					cc += (b - a) << (k << 2);
					cc += (a - b) << ((i + j - k) << 2);
				}
				if (ddis.find(cc) == ddis.end()) {
					ddis[cc] = ddis[cn] + 1;
					QQ.push(cc);
				}
				else if (ddis[cc] > ddis[cn] + 1) {
					ddis[cc] = ddis[cn] + 1;
					QQ.push(cc);
				}
			}
		}
	}
	int ans = 100;
	for (auto i : dis) {
		if (ddis.find(i.first) == ddis.end())continue;
		ans = min(i.second + ddis[i.first], ans);
	}
	cout << ans << endl;
	return 0;
}