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 <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <valarray>
#include <vector>

#define EPS 1e-9
#define INF 1070000000LL
#define MOD 1000000007LL
#define fir first
#define foreach(it,X) for(__typeof((X).begin()) it=(X).begin();it!=(X).end();it++)
#define ite iterator
#define mp make_pair
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define pb push_back
#define sec second
#define sz(x) ((int)(x).size())

using namespace std;

struct timer{
	time_t start;
	timer(){start=clock();}
	~timer(){cerr<<1.*(clock()-start)/CLOCKS_PER_SEC<<" secs"<<endl;}
};

typedef istringstream iss;
typedef long long ll;
typedef pair<int,int> pi;
typedef stringstream sst;
typedef vector<int> vi;

int N,A[11];
map<vi,int> M[2];

void bfs(vi start,int mode){
	queue<vi> Q;
	Q.push(start);
	M[mode][start]=0;
	while(sz(Q)){
		vi v=Q.front();Q.pop();
		int d=M[mode][v];
		if(d==4)break;
		rep(i,N)rep2(j,i+1,N){
			vi w=v;
			rep2(k,i,j+1){
				w[k] = v[j-(k-i)];
			}
			if(M[mode].find(w)==M[mode].end()){
				M[mode][w]=d+1;
				Q.push(w);
			}
		}
	}
}

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	
	cin>>N;
	rep(i,N)cin>>A[i],A[i]--;
	
	vi v;
	rep(i,N)v.pb(A[i]);
	bfs(v,0);
	v.clear();
	rep(i,N)v.pb(i);
	bfs(v,1);
	int ans=9;
	foreach(it,M[0]){
		if(M[1].find(it->fir)!=M[1].end()){
			ans=min(ans,it->sec+M[1][it->fir]);
		}
	}
	cout<<ans<<endl;
}