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<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
#include<map>

using namespace std;

#define reps(i,f,n) for(int i=f;i<n;i++)
#define rep(i,n) reps(i,0,n)

typedef long long ll;
const int INF = 1e9+7;


int n;
vector<int> in;


void input(){
	cin>>n;
	rep(i,n){
		int t;
		cin>>t;
		in.push_back(t);
	}
}


ll getHash(vector<int>& a){
	ll ret=0, t=1;
	rep(i,a.size()){
		ret += a[i]*t;
		t*=11;
	}
	return ret;
}

void reverse(vector<int>& a, int b, int c){
	while(b<c){
		swap(a[b], a[c]);
		b++; c--;
	}
}

map<ll,int> memo;

int ans = INF;


void saiki(vector<int>& a, int mode, int depth, int limit){
	
	if(mode==0){
		bool ok = true;
		rep(i,a.size()){
			if(a[i]!=i+1)ok=false;
		}
		if(ok)ans = min(ans, depth);
	}

	if(mode==1){
		ll h = getHash(a);
		if(memo.find(h)!=memo.end()){
			int s = memo[h] + depth;
			ans = min(ans, s);
			return;
		}
	}

	if(depth==limit){
		if(mode==0)memo[getHash(a)] = depth;
		return;
	}


	rep(i,a.size()){
		reps(j,i+1,a.size()){
			reverse(a, i ,j);
			saiki(a, mode, depth+1, limit);
			reverse(a,i,j);
		}
	}
}

int solve(){
	vector<int> tmp;
	rep(i,in.size())tmp.push_back(i+1);

	ans = in.size()-1;

	int limit = (in.size()-1)/2;

	saiki(in, 0, 0, limit);
	saiki(tmp, 1, 0, limit);

	return ans;
}

int main(){
	input();
	cout<<solve()<<endl;
}