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 <vector>
#include <set>
#include <algorithm>
using namespace std;

typedef long long LL;

int n;

LL encode(const vector<char> &v){
	LL a = 0;
	for(int i = 0; i < n; ++i){
		a |= (LL)v[i] << (i << 2);
	}
	return a;
}

vector<char> decode(LL x){
	vector<char> v(n);
	for(int i = 0; i < n; ++i){
		v[i] = (x >> (i << 2)) & 15;
	}
	return v;
}

int main(){
	scanf("%d", &n);
	
	vector<char> s(n), goal(n);
	int x;
	for(int i = 0; i < n; ++i){
		scanf("%d", &x);
		s[i] = x;
		goal[i] = i + 1;
	}
	
	if( s == goal ){
		puts("0");
		return 0;
	}

	vector<LL> v1, v2;
	v1.push_back( encode(s) );
	v2.push_back( encode(goal) );
	
	set<LL> old;
	old.insert( v1[0] );
	old.insert( v2[0] );

	int a;
	for(int a = 1; ; ++a){
		vector<LL> tmp;
		
		for(int i = 0; i < v1.size(); ++i){
			s = decode( v1[i] );
			for(int j = 0; j < n - 1; ++j)
			for(int k = j + 2; k <= n; ++k){
				vector<char> t = s;
				reverse(t.begin() + j, t.begin() + k);
				LL u = encode(t);

				if( binary_search(v2.begin(), v2.end(), u) ){
					printf("%d\n", a);
					return 0;
				}
				
				if( old.find(u) == old.end() ){
					old.insert(u);
					tmp.push_back(u);
				}
			}
		}
		
		sort(tmp.begin(), tmp.end());
		v1.swap(tmp);
		
		v1.swap(v2);
	}
}