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 <bits/stdc++.h>
using namespace std;

template<class T>
ostream &operator<<(ostream &os,const vector<T> &v){
	for(int i = 0;i < v.size();i++) os << (i ? "," : "[") << v[i];
	os << "]";
	return os;
}

int n;
vector<int> a;

map<vector<int>,int> bfs(vector<int> s){
	map<vector<int>,int> dist;
	dist[s] = 0;
	queue<vector<int>> que;
	que.push(s);
	while(!que.empty()){
		vector<int> v = que.front(); que.pop();
		if(dist[v] >= 4) break;
		for(int i = 1;i <= 2 * n - 3;i++){
			vector<int> to = v;
			for(int j = !(i % 2) + 1;;j += 2){
				if(i - j < 0 || i + j >= 2 * n - 1) break;
				int x = (i - j) / 2,y = (i + j) / 2;
				swap(to[x],to[y]);
				if(!dist.count(to)){
					dist[to] = dist[v] + 1;
					que.push(to);
				}
			}
		}
	}
	return dist;
}

signed main(){
	cin >> n;
	a.resize(n);
	for(int i = 0;i < n;i++){
		cin >> a[i]; a[i]--;
	}
	vector<int> vec(n);
	iota(vec.begin(),vec.end(),0);
	auto dist1 = bfs(vec),dist2 = bfs(a);
	int ans = n - 1;
	do{
		if(dist1.count(vec) && dist2.count(vec)){
			ans = min(ans,dist1[vec] + dist2[vec]);
		}
	}while(next_permutation(vec.begin(),vec.end()));
	cout << ans << endl;
}