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<stdio.h>
#include<algorithm>
using namespace std;
int b[10];
long long c[5][4200000];
long long d[5][4200000];
int C[5];
int D[5];
long long p10[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000LL};
int main(){
	int a;scanf("%d",&a);
	long long S=0;
	for(int i=0;i<a;i++){
		scanf("%d",b+i);
		b[i]--;
		S*=10;
		S+=b[i];
	}
	int ans=a-1;
	int start=123456789;
	for(int i=0;i<10-a;i++)start/=10;
	c[0][C[0]++]=start;
	d[0][D[0]++]=S;
	for(int i=0;i<4;i++){
	//	printf("%d %d\n",C[i],D[i]);
		for(int j=0;j<C[i];j++){
			for(int k=0;k<a;k++){
				for(int l=k+1;l<a;l++){
					long long TO=0;
					for(int m=0;m<a;m++){
						TO*=10;
						if(k<=m&&m<=l)TO+=c[i][j]%p10[a-k-l+m]/p10[a-k-l+m-1];
						else TO+=c[i][j]%p10[a-m]/p10[a-1-m];
					}
					c[i+1][C[i+1]++]=TO;
				}
			}
		}
		for(int j=0;j<D[i];j++){
			for(int k=0;k<a;k++){
				for(int l=k+1;l<a;l++){
					long long TO=0;
					for(int m=0;m<a;m++){
						TO*=10;
						if(k<=m&&m<=l)TO+=d[i][j]%p10[a-k-l+m]/p10[a-k-l+m-1];
						else TO+=d[i][j]%p10[a-m]/p10[a-1-m];
					}
					d[i+1][D[i+1]++]=TO;
				}
			}
		}
	}
	for(int i=0;i<5;i++){
		std::sort(d[i],d[i]+D[i]);
	}
	for(int i=0;i<a-1;i++){
		int n=i/2;
		bool ok=false;
		for(int j=0;j<C[n];j++)if(binary_search(d[i-n],d[i-n]+D[i-n],c[n][j]))ok=true;
		if(ok){
			printf("%d\n",i);
			return 0;
		}
	}
	printf("%d\n",ans);
}