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<map>
#include<queue>
#include<cstdio>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

void bfs(vector<int> a,map<vector<int>,int> &memo){
	int n=a.size();
	memo[a]=0;
	queue< pair< int,vector<int> > > Q; Q.push(make_pair(0,a));
	while(!Q.empty()){
		int t=Q.front().first;
		vector<int> a=Q.front().second; Q.pop();

		if(t==4) break;

		rep(l,n) for(int r=l+1;r<n;r++) {
			reverse(a.begin()+l,a.begin()+r+1);
			if(memo.count(a)==0){
				memo[a]=t+1;
				Q.push(make_pair(t+1,a));
			}
			reverse(a.begin()+l,a.begin()+r+1);
		}
	}
}

int main(){
	int n; scanf("%d",&n);
	vector<int> a(n);
	rep(i,n) scanf("%d",&a[i]);

	map<vector<int>,int> memo1,memo2;
	bfs(a,memo1);
	sort(a.begin(),a.end());
	bfs(a,memo2);

	int ans=9;
	map<vector<int>,int>::iterator it;
	for(it=memo1.begin();it!=memo1.end();++it) if(memo2.count(it->first)>0) ans=min(ans,it->second+memo2[it->first]);
	printf("%d\n",ans);

	return 0;
}