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<algorithm>
#include<iomanip>
#include<queue>
#include<vector>
#include<complex>
#include<map>
#include<set>
using namespace std;
#define int long long
vector<int> SS;
int hs(vector<int> &X) {
	int res = 0;
	for (int i = 0; i < X.size(); i++) {
		res += X[i];
		res *= 10;
	}
	return res;
}
signed main() {
	int N;
	cin >> N;
	vector<int> A(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		A[i]--;
	}

	queue<int > qu;
	map<int, int> mp;
	vector<int> B(N);
	for (int i = 0; i < N; i++) {
		B[i] = i;
	}
	int pow10[12];
	pow10[0] = 1;
	for (int i = 1; i <= 11; i++) {
		pow10[i] = pow10[i - 1] * 10;
	}
	mp[hs(B)] = 0;

	qu.push(hs(B));
	/*{
		int r = 5;
		int l = 0;
		int hh = hs(B);
		hh += pow10[N - l] * (B[r] - B[l]);
		hh += pow10[N - r] * (B[l] - B[r]);
		swap(B[l], B[r]);
		cerr << hh << " " << hs(B) << endl;
	}*/
	vector<int> t(N);
	vector<int> t2;
	int cnt = 0;
	int l, r;
	int z = 0;
	while (!qu.empty()) {

		z = qu.front(); qu.pop();
		int h;
		h = z;
		z /= 10;
		for (int i = N - 1; i >= 0; i--) {
			t[i] = z % 10;
			z /= 10;
		}
		
		int ht = h;
		int a = mp[h];
		/*if (cnt % 100000 == 0) {
			cerr << a << " " << qu.size() << " " << mp.size() << endl;
		}
		cnt++;*/
		//cerr << h << endl;
		for (int i = 0; i < N; i++) {

			for (int j = 1; j <= 2; j++) {
				l = i;
				r = i + j;
				h = ht;
				while (l >= 0 && r < N) {
					h += pow10[N - l] * (t[r] - t[l]);
					h += pow10[N - r] * (t[l] - t[r]);
					//cerr << h << " " << l << " " << r << endl;
					auto m = mp.find(h);
					if (m == mp.end() || (*m).second > a + 1) {
						mp[h] = a + 1;
						if (a + 1 <= 4) {
							qu.push(h);
						}
					}
					l--;
					r++;
				}
			}
		}
		//break;
	}
	vector<int> C(N);
	for (int i = 0; i < N; i++) {
		C[A[i]] = i;
	}
	int res = 9;
	int p = 0;
	for (auto t : mp) {
		p = t.first;
		p /= 10;
		for (int i = N - 1; i >= 0; i--) {
			B[i] = C[p % 10];
			p /= 10;
		}
		auto k = mp.find(hs(B));
		if (k != mp.end()) {
			res = min(res, t.second + (*k).second);
		}
	}
	cout << res << endl;
}