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 <cstdio>
#include <vector>
#include <map>
#include <string>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;

void debug(const vector<int>& v, int c=0){
	cout << "{";
	for(int i=0 ; i < v.size() ; i++ ){
		cout << v[i];
		if( i+1 != v.size() ) cout << ", ";
	}
	cout << "} cost:" << c << endl;
}

int main(){
	int n;
	cin >> n;
	
	vector<int> a(n), b(n);
	for(int i=0 ; i < n ; i++ ){
		cin >> a[i];
		b[i] = i+1;
	}
	// d[v] := スタートからのコスト, h[v] := ゴールからの距離
	map<vector<int>,int> d, h;
	// 解は最大でも n-1 
	int ans = n-1;
	// ゴールから探索
	{
		h[b] = 0;
		queue<vector<int> > q;
		q.push( b );
		while( !q.empty() ){
			vector<int> v = q.front();
			int cost = h[v];
			q.pop();
			
			if( v == a ){
				ans = cost;
				break;
			}
			if( cost >= 4 ) break;
			
			for(int i=0 ; i < n ; i++ ){
				for(int j=i+1 ; j < n ; j++ ){
					vector<int> next = v;
					//debug(v,cost);
					reverse( next.begin()+i , next.begin()+j+1 );
					//cout << "reveese(" << i << "," << j << ")" << endl;
					//debug(next,cost);
					//cout << endl;
					if( !h.count(next) ){
						h[next] = cost+1;
						q.push(next);
					}
				}
			}
		}
	}
	// スタートから探索
	{
		d[a] = 0;
		queue<vector<int> > q;
		q.push( a );
		while( !q.empty() ){
			vector<int> v = q.front();
			int cost = d[v];
			q.pop();
			
			if( h.count(v) ){
				ans = cost + h[v];
				break;
			}
			if( cost >= 4 ) break;
			
			for(int i=0 ; i < n ; i++ ){
				for(int j=i+1 ; j < n ; j++ ){
					vector<int> next = v;
					reverse( next.begin()+i , next.begin()+j+1 );
					if( !d.count(next) ){
						d[next] = cost+1;
						q.push(next);
					}
				}
			}
		}
	}
	cout << ans << endl;
}