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

#include <queue>
using namespace std;
typedef long long ll;
int n;
ll perm[11];
int dist[4000000];
bool check[4000000];
map<ll,int> ma;

void permutation2(){
	for(int i=0;i<n;i++){
		perm[i]=i;
	}
	int j=0;
	do{
		ll d=0;
		ll p=1;
		for(int i=0;i<n;i++){
			d+=perm[i]*p;
			p*=10LL;
		}
		ma[d]=j;
		j++;
	}while(next_permutation(perm,perm+n));
}


int a[11];
ll tmp[11];
ll ten[11];

int bfs2(ll s){
	queue<ll> que;
	que.push(s);
	dist[ma[s]]=0;
	int res=n-1;
	while(que.size()){
		ll v=que.front();
		que.pop();
		int lv=ma[v];
		if(dist[lv]==4)continue;
		ll nv=v;
		for(int i=0;i<n;i++){
			tmp[i]=nv%10LL;
			nv/=10LL;
		}
		ll dv=v;
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++){
				ll uv=dv;
				for(int k=0;i+k<j-k;k++){
					uv+=tmp[i+k]*(ten[j-k]-ten[i+k])+tmp[j-k]*(ten[i+k]-ten[j-k]);
				}
				int nexv=ma[uv];
				if(dist[nexv]==-1){
					dist[nexv]=dist[lv]+1;
					que.push(uv);
				}else if(check[nexv]){
					res=min(res,dist[lv]+dist[nexv]+1);
				}
			}
		}
	}
	return res;
}

int bfs(ll s){
	queue<ll> que;
	que.push(s);
	memset(dist,-1,sizeof(dist));
	memset(check,false,sizeof(check));
	dist[ma[s]]=0;
	check[ma[s]]=true;
	while(que.size()){
		ll v=que.front();
		que.pop();
		int lv=ma[v];
		if(lv==0)return dist[lv];
		if(dist[lv]==4)continue;
		ll nv=v;
		for(int i=0;i<n;i++){
			tmp[i]=nv%10LL;
			nv/=10LL;
		}
		ll dv=v;
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++){
				ll uv=dv;
				for(int k=0;i+k<j-k;k++){
					uv+=tmp[i+k]*(ten[j-k]-ten[i+k])+tmp[j-k]*(ten[i+k]-ten[j-k]);
				}
				int nexv=ma[uv];
				if(dist[nexv]==-1){
					dist[nexv]=dist[lv]+1;
					check[nexv]=true;
					que.push(uv);
				}
			}
		}
	}
	return -1;
}

int main(void){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
		a[i]--;
	}
	ll s=0;
	ll p=1;
	for(int i=0;i<n;i++){
		s+=(ll)p*a[i];
		ten[i]=p;
		p*=10LL;
	}
	permutation2();
	int re=bfs(s);
	if(re!=-1)printf("%d\n",re);
	else{
		sort(a,a+n);
		s=0;
		p=1;
		for(int i=0;i<n;i++){
			s+=(ll)p*a[i];
			p*=10LL;
		}
		printf("%d\n",bfs2(s));
	}
	return 0;
}