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<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<unordered_map>
#include<unordered_set>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod
ll n;
ll po[10];
ll has(vector<ll> a){
	ll x=1,res=0;
	rep(i,n){
		res+=a[i]*x;
		x*=10;
	}
	return res;
}
vector<ll> unzip(ll key){
	vector<ll> a;
	rep(i,n){
		a.push_back(key%10);
		key/=10;
	}
	return a;
}

class HALF{
public:
unordered_set<ll> vis;
unordered_map<ll,ll> dist;
queue<P> Q;
void solve(ll key,ll cost){
	dist[key]=cost;
	vector<ll> a=unzip(key);
	for(int j=0;j+1<n;j++){
		vector<ll> b=a;
		ll score=key;
		for(int i=0;0<=j-i&&j+1+i<n;i++){
			score-=b[j-i]*po[j-i];
			score-=b[j+1+i]*po[j+1+i];
			swap(b[j-i],b[j+1+i]);
			score+=b[j-i]*po[j-i];
			score+=b[j+1+i]*po[j+1+i];
			if(cost<4&&!vis.count(score)){
				Q.push(make_pair(score,cost+1));
				vis.insert(score);
			}
		}
	}
	for(int j=1;j<n-1;j++){
		vector<ll> b=a;
		ll score=key;
		for(int i=1;0<=j-i&&j+i<n;i++){
			score-=b[j-i]*po[j-i];
			score-=b[j+i]*po[j+i];
			swap(b[j-i],b[j+i]);
			score+=b[j-i]*po[j-i];
			score+=b[j+i]*po[j+i];
			if(cost<4&&!vis.count(score)){
				Q.push(make_pair(score,cost+1));
				vis.insert(score);
			}
		}
	}
}
void main(vector<ll> a){
	vis.insert(has(a));
	Q.push(make_pair(has(a),0));
	while(!Q.empty()){
		ll key=Q.front().first,cost=Q.front().second;
		Q.pop();
		solve(key,cost);
	}
}
};
HALF s,t;
int main(){
	po[0]=1;
	for(int i=1;i<10;i++)po[i]=po[i-1]*10;
	vector<ll> a;
	cin>>n;
	rep(i,n)a.push_back(i);
	s.main(a);
	rep(i,n){
		ll x; cin>>x; x--;
		a[i]=x;
	}
	t.main(a);
	ll ans=n-1;
	for(auto u:s.vis){
		if(t.vis.count(u)){
			chmin(ans,s.dist[u]+t.dist[u]);
		}
	}
	cout<<ans<<endl;
}