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

using namespace std;

int N,k;

long long encode(vector<int> a){
	long long res=0;
	long long coe=1;
	for(int i=0;i<N;i++){
		res+=coe*a[i];
		coe*=10;
	}
	return res;
}

vector<int> decode(long long x){
	vector<int> res;
	for(int i=0;i<N;i++){
		res.push_back(x%10);
		x/=10;
	}
	return res;
}

map<long long,int> dis[2];

void bfs(long long s,int id){
	map<long long,int> &res=dis[id];
	queue<long long> que;
	que.push(s);
	res[s]=0;
	while(!que.empty()){
		long long cur=que.front();
		que.pop();
		int d=res[cur];
		if(d>=k) continue;
		vector<int> a=decode(cur);
		for(int i=0;i<N;i++) for(int j=i+1;j<N;j++){
			int tmp[10];
			for(int k=i;k<=j;k++) tmp[k]=a[k];
			for(int k=i;k<=j;k++) a[k]=tmp[i+j-k];
			long long nxt=encode(a);
			if(res.count(nxt)>0&&res[nxt]<=d+1){}
			else{
				que.push(nxt);
				res[nxt]=d+1;
			}
			for(int k=i;k<=j;k++) a[k]=tmp[k];
		}
	}
}

int main(){
	scanf("%d",&N);
	k=(N-1)/2;
	vector<int> s,t;
	for(int i=0;i<N;i++){
		s.push_back(i);
		int in;
		scanf("%d",&in);
		t.push_back(in-1);
	}
	long long s_=encode(s);
	long long t_=encode(t);
	bfs(s_,0);
	bfs(t_,1);
	int ans=N-1;
	map<long long,int>::iterator it1=dis[0].begin(),it2=dis[1].begin();
	for(;;){
		if(it1==dis[0].end()||it2==dis[1].end()) break;
		if(it1->first==it2->first){
			ans=min(ans,it1->second+it2->second);
			it1++;it2++;
		}else if(it1->first<it2->first) it1++;
		else it2++;
	}
	printf("%d\n",ans);
	return 0;
}