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 <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <unordered_map>

using namespace std;
typedef long long int ll;
typedef pair<ll, int> P;
const int INF=100;

int f[11], n;
ll p10[11];
int d[2][3628801];
int a[10], a1[10], a2[10], ct[10];
int a2v; ll a2c;

void fac(){
	f[0]=1, p10[0]=1;
	for(int i=1; i<=n; i++){
		f[i]=f[i-1]*i;
		p10[i]=p10[i-1]*10;
    }
}

void swp(int x, int y){
	a2c=a2c+(ll)(a2[y]-a2[x])*p10[x]+(ll)(a2[x]-a2[y])*p10[y];
	swap(a2[x], a2[y]);
	int c1=0, c2=0;
	for(int k=x+1; k<y; k++){
		if(a2[k]<a2[x]) c1++;
		if(a2[k]<a2[y]) c2++;
	}
	if(a2[x]<a2[y]) a2v=a2v-f[n-1-y];
	else a2v=a2v+f[n-1-x];
	a2v=a2v+(ct[y]+c1-ct[x])*f[n-1-x]+(ct[x]-c2-ct[y])*f[n-1-y];
	for(int k=x+1; k<y; k++){
		if(a2[x]<a2[k] && a2[y]>a2[k]){
			a2v-=f[n-1-k];
		}else if(a2[x]>a2[k] && a2[y]<a2[k]){
			a2v+=f[n-1-k];
		}
	}
}

int main()
{
	cin>>n;
	for(int i=0; i<n; i++){
		cin>>a[i]; a[i]--;
	}
	fac();
	for(int t=0; t<2; t++){
		ll ac=0; int aval=0;
		if(t==0){
			for(int i=0; i<n; i++){
				ac+=((ll)a[i])*p10[i];
				int ct=a[i];
				for(int j=0; j<i; j++){
					if(a[j]<a[i]) ct--;
				}
				aval+=(ct*f[n-1-i]);
			}
			if(aval==0){
				cout<<0<<endl;
				return 0;
			}
		}else{
			for(ll i=0; i<n; i++){
				ac+=(i*p10[i]);
			}
		}
		queue<ll> que;
		fill(d[t], d[t]+f[n], INF);
		d[t][aval]=0;
		que.push(ac);
		while(!que.empty()){
			ll a1c=que.front(); que.pop();
			ll a1c1=a1c;
			for(int i=0; i<n; i++){
				a1[i]=a1c1%10;
				a1c1/=10;
			}
			int a1v=0;
			for(int i=0; i<n; i++){
				ct[i]=a1[i];
				for(int j=0; j<i; j++){
					if(a1[j]<a1[i]) ct[i]--;
				}
				a1v+=(ct[i]*f[n-1-i]);
			}
			int d1=d[t][a1v];
			if(d1==4) break;
			for(int i=1; i<n-1; i++){
				for(int j=0; j<n; j++) a2[j]=a1[j];
				a2v=a1v; a2c=a1c;
				for(int j=1; (i-j>=0 && i+j<n); j++){
					swp(i-j, i+j);
					if(d[t][a2v]==INF){
						d[t][a2v]=d1+1;
						if(t==0 && a2v==0){
							cout<<d[t][a2v]<<endl;
							return 0;
						}
						que.push(a2c);
					}
				}
			}
			for(int i=0; i<n-1; i++){
				for(int j=0; j<n; j++) a2[j]=a1[j];
				a2v=a1v; a2c=a1c;
				for(int j=0; (i-j>=0 && i+j+1<n); j++){
					swp(i-j, i+j+1);
					if(d[t][a2v]==INF){
						d[t][a2v]=d1+1;
						if(t==0 && a2v==0){
							cout<<d[t][a2v]<<endl;
							return 0;
						}
						que.push(a2c);
					}
				}
			}
		}
	}
	int ans=INF;
	for(int i=0; i<f[n]; i++){
		ans=min(ans, d[0][i]+d[1][i]);
	}
	if(ans==INF){
		cout<<9<<endl;
	}else{
		cout<<ans<<endl;
	}
	return 0;
}