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>

using namespace std;

short N;

struct Array{
	short a[10], d;
	Array(){}
	bool operator==(const Array &obj)const{
		for(short i = 0; i < N; i++){
			if(a[i] != obj.a[i]) return false;
		}
		return true;
	}
	bool operator<(const Array &obj)const{
		for(short i = 0; i < N; i++){
			if(a[i] < obj.a[i]) return true;
			if(a[i] > obj.a[i]) return false;
		}
		return d < obj.d;
	}
};

Array A, I;
vector<Array> vec, vec2;

void dfs(Array arr, short dep, vector<Array> &vec)
{
	vec.push_back(arr);
	if(dep == 4) return;
	
	Array tmp;
	for(short i = 0; i < N; i++){
		for(short j = 0; j < N; j++){
			if(i >= j) continue;
			for(short k = 0; k < N; k++) tmp.a[k] = arr.a[k];
			for(short k = i; k <= j; k++) tmp.a[k] = arr.a[j-(k-i)];
			tmp.d = arr.d + 1;
			dfs(tmp, dep+1, vec);
		}
	}
}

int main(void)
{
	cin >> N;
	for(short i = 0; i < N; i++) cin >> A.a[i];
	for(short i = 0; i < N; i++) I.a[i] = i+1;
	A.d = I.d = 0;
	
	dfs(A, 0, vec);
	dfs(I, 0, vec2);
	
	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());
	
	sort(vec2.begin(), vec2.end());
	vec2.erase(unique(vec2.begin(), vec2.end()), vec2.end());
	
	short ans = N-1;
	Array tmp;
	for(short i = 0; i < vec.size(); i++){
		tmp = vec[i]; tmp.d = 0;
		auto p = lower_bound(vec2.begin(), vec2.end(), tmp);
		if(*p == vec[i]){
			ans = min(ans, (short)(p->d + vec[i].d));
		}
		if(vec[i] == I) ans = min(ans, vec[i].d);
	}
	
	cout << ans << endl;
	
	return 0;
}