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 <map>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>

using namespace std;

typedef long long ll;

struct Node {
	ll hash;
	int l, r;
};

int N;

ll toHash(vector<int> v) {
	ll ret = 0;
	for (int i = 0; i < N; ++i) {
		ret *= 10;
		ret += v[i];
	}
	return ret;
}
vector<int> fromHash(ll hash) {
	vector<int> ret(N);
	for (int i = 0; i < N; ++i) {
		ret[N-i-1] = hash % 10;
		hash /= 10;
	}
	return ret;
}

int main() {
	cin >> N;

	vector<int> v(N);
	for (int i = 0; i < v.size(); ++i) {
		cin >> v[i]; --v[i];
	}

	vector<int> g = v;
	sort(g.begin(), g.end());

	map<ll, int> m;
	queue<Node> Q[10]; Q[0].push( (Node){ toHash(v), 0, 0 } );
	for (int step = 0; step < max(1, N/2); ++step) {
		while ( !Q[step].empty() ) {
			Node node = Q[step].front(); Q[step].pop();
			ll hash = node.hash;
			int l = node.l, r = node.r;

			if (m.find(hash) != m.end()) continue;
			m[hash] = step;

			vector<int> v = fromHash(hash);

			if (step+1 < N) {
				for (int i = 0; i < N; ++i) {
					for (int j = i+1; j < N; ++j) {
						if (l <= i && j <= r) continue;

						vector<int> nv = v;
						reverse(nv.begin()+i, nv.begin()+j+1);

/*
						bool f = true;
						for (int k = i+1; k < j; ++k) {
							if (nv[k] != k) f = false;
						}
						if (f) */
						Q[step+1].push( (Node){ toHash(nv), i, j } );
					}
				}
			}
		}
	}

	set<ll> s;
	for (int i = 0; i < N; ++i) {
		while ( !Q[i].empty() ) {
			Q[i].pop();
		}
	}
	Q[0].push( (Node){ toHash(g), 0, 0 } );
	for (int step = 0; step < N; ++step) {
		while ( !Q[step].empty() ) {
			Node node = Q[step].front(); Q[step].pop();
			ll hash = node.hash;
			int l = node.l, r = node.r;

			if (m.find(hash) != m.end()) {
				cout << m[hash]+step << endl;
				return 0;
			}
			if (s.find(hash) != s.end()) continue;
			s.insert(hash);

			vector<int> v = fromHash(hash);

			if (step+1 < N) {
				for (int i = 0; i < N; ++i) {
					for (int j = i+1; j < N; ++j) {
						if (l <= i && j <= r) continue;

						vector<int> nv = v;
						reverse(nv.begin()+i, nv.begin()+j+1);

/*
						bool f = true;
						for (int k = i+1; k < j; ++k) {
							if (nv[k] != k) f = false;
						}
						if (f) */
						Q[step+1].push( (Node){ toHash(nv), i, j } );
					}
				}
			}
		}
	}
}