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:
//-O2 is required.
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef vector<int> V;
map<V,int>m;
//map<V,pair<pair<int,int>,V> >track;
//V v1,v2;
pair<int,int>vec2nvec;
int bfs(V &v, int back){
	if(!back&&m.find(v)!=m.end()){
		//v1.clear();
		//vec2nvec=make_pair(0,0);
		//v2=v;
		return m[v];
	}
	set<V>s;
	queue<pair<V,int> >q;
	if(back)m[v]=0;
	s.insert(v);
	int i,j;
	for(q.push(make_pair(v,0));!q.empty();){
		V vec=q.front().first;
		int depth=q.front().second;
		q.pop();
		if(back&&depth>3)return 0;
		for(i=0;i<vec.size();i++)
			for(j=i+1;j<vec.size();j++){
				V nvec=vec;
				reverse(nvec.begin()+i,nvec.begin()+j+1);
				if(!back&&m.find(nvec)!=m.end()){
					//v1=vec;
					//vec2nvec=make_pair(i,j);
					//v2=nvec;
					return depth+1+m[nvec];
				}
				if(!s.insert(nvec).second)continue;
				if(back)m[nvec]=depth+1;
				//track[nvec]=make_pair(make_pair(i,j),vec);
				q.push(make_pair(nvec,depth+1));
			}
	}
	return 0;
}
//void backtrack(V &v){
//	if(track.find(v)==track.end())return;
//	backtrack(track[v].second);
//	printf("%d %d\n",track[v].first.first+1,track[v].first.second+1);
//}
//void forwardtrack(V &v){
//	if(track.find(v)==track.end())return;
//	printf("%d %d\n",track[v].first.first+1,track[v].first.second+1);
//	forwardtrack(track[v].second);
//}
int main(){
	V prob;
	int i=0,t,n;
	for(scanf("%d",&n);i<n;i++){
		if(scanf("%d",&t)==-1)return 0;
		prob.push_back(t);
	}
	V goal=prob;
	sort(goal.begin(),goal.end());
	bfs(goal,1);
	printf("%d\n",bfs(prob,0));
	//backtrack(v1);
	//if(vec2nvec.first!=vec2nvec.second)printf("%d %d\n",vec2nvec.first+1,vec2nvec.second+1);
	//forwardtrack(v2);
}