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 <vector>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
typedef long long int lli;

//16進法
inline lli Reverse(lli n, int l, int r){
	lli ret = 0;
	for(int i=0; i<10; i++){
		lli num = n & 0b1111;
		n >>= 4;
		if(l<=i && i<=r){
			ret |= num << (4*(l+r-i));
		}else{
			ret |= num << (4*i);
		}
	}
	return ret;
}

int main(){
	int n;
	cin >> n;
	lli num[2] = {0, 0};
	for(int i=0; i<n; i++){
		lli a;
		cin >> a;
		num[0] |= a << (4*i);
		num[1] |= (lli)(i+1) << (4*i);
	}
	
	map<lli, int> step[2];
	for(int r=0; r<2; r++){
		set<lli> prev;
		prev.insert(num[r]);
		step[r][num[r]] = 0;
		for(int s=0; s<(n-1)/2; s++){
			set<lli> next;
			for(lli arr: prev){
				for(int i=0; i<n; i++){
					for(int j=i+1; j<n; j++){
						lli rev = Reverse(arr, i, j);
						if(step[r].count(rev) == 0){
							step[r][rev] = s+1;
							next.insert(rev);
						}
					}
				}
			}
			prev = next;
		}
	}
	
	int ans = n-1;
	for(auto itr: step[0]){
		if(step[1].count(itr.first) != 0){
			ans = min(ans, itr.second +step[1][itr.first]);
		}
	}
	cout << ans << endl;
	return 0;
}