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 <unordered_set>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
typedef pair<ll,int> pli;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = (n)-1; i >= 0; i--)

int main() {
	int N; cin >> N;
	vector<int> A(N); rep(i,N) cin >> A[i];
	ll tmp = 0, gl = 0;
	rep(i,N) {
		tmp *= 10;
		tmp += A[i]-1;
		gl *= 10;
		gl += i;
	}
	vector<pli> candidate[2];
	rep(a,2) {
		queue<pli> q;
		q.push(pli(!a ? tmp : gl, 0));
		unordered_set<ll> used;
		used.insert(q.front().first);
		while(q.size()) {
			candidate[a].push_back(q.front());
			ll t = q.front().first;
			ll turn = q.front().second; q.pop();
			if(turn > 4) break;
			vector<int> v(N);
			rrep(i,N) {
				v[i] = t % 10;
				t /= 10;
			}
			rep(i,N) {
				for(int j = i+1; j < N; j++) {
					vector<int> vv = v;
					ll nx = 0;
					reverse(vv.begin()+i, vv.begin()+j+1);
					rep(i,N) {
						nx *= 10;
						nx += vv[i];
					}
					if(used.find(nx) == used.end()) {
						used.insert(nx);
						q.push(pli(nx,turn+1));
					}
				}
			}
		}
		sort(candidate[a].begin(), candidate[a].end());
	}
	int res = 9;
	rep(i,candidate[0].size()) {
		int indx;
		indx = lower_bound(candidate[1].begin(), candidate[1].end(), candidate[0][i])
			- candidate[1].begin();
		if(candidate[0][i].first == candidate[1][indx].first) {
			res = min(res, candidate[0][i].second+candidate[1][indx].second);
		}
	}
	cout << res << endl;
}