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 <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


struct Info{
	Info(ll arg_number,int arg_swap_count){
		number = arg_number;
		swap_count = arg_swap_count;
	}

	ll number;
	int swap_count;
};


int N,ans;
ll sorted_num;
map<ll,int> MAP,rev_MAP;

int main(){

	scanf("%d",&N);

	ll first = 0,array[10],before[10],order[10];
	for(int i = 0; i < N; i++){
		scanf("%lld",&array[i]);
		before[i] = array[i];
	}

	sort(array,array+N);
	order[0] = 0;
	for(int i = 1; i < N; i++){
		if(array[i] != array[i-1]){
			order[i] = order[i-1]+1;
		}else{
			order[i] = order[i-1];
		}
	}

	for(int i = 0; i < N; i++){
		for(int k = 0; k < N; k++){
			if(before[i] == array[k]){ //大きさの順位を足す(0～9)
				first = 10*first+order[k];
			}
		}
	}

	//最終形を求める(簡単のため、0,1,2..と置き換える)
	sorted_num = 0;
	for(int i = 0; i < N; i++){
		sorted_num = 10*sorted_num+order[i];
	}

	//printf("first:%lld sorted:%lld\n",first,sorted_num);

	if(first == sorted_num){
		printf("0\n");
		return 0;
	}

	MAP[sorted_num] = N-1; //交換回数は最大でN-1回(左端から、正しいものを配置していけば良い)

	queue<Info> Q;

	ll calc_array[10],work[10],tmp,next_number;
	int swap_count,index;
	stack<ll> S;

	//両側探索:まずfirst側から、最大で深さ4回、変化の枝を走らせる
	Q.push(Info(first,0));

	ans = N-1;

	while(!Q.empty()){

		//数字を配列表現に直す
		tmp = Q.front().number;
		//printf("tmp:%lld\n",tmp);
		swap_count = Q.front().swap_count;
		Q.pop();

		if(swap_count+1 >= ans)continue;

		while(tmp > 0){
			S.push(tmp%10);
			tmp /= 10;
		}

		index = 0;
		while(!S.empty()){

			calc_array[index++] = S.top();
			S.pop();
		}

		if(index < N){ //先頭に0が(複数)来ている場合、0を補充する

			/*printf("array\n");
			for(int i = 0; i < index; i++){
				printf("%lld",calc_array[i]);
			}
			printf("\n");
*/
			for(int i = index-1; i >=0; i--){
				calc_array[i+(N-index)] = calc_array[i];
			}
			for(int i = 0; i < N-index; i++){
				calc_array[i] = 0;
			}

			/*printf("aftery\n");
						for(int i = 0; i < index+1; i++){
							printf("%lld",calc_array[i]);
						}
						printf("\n");*/
		}

		for(int i = 0; i < N-1; i++){
			for(int k = i+1; k < N; k++){
				for(int p = 0; p < N; p++)work[p] = calc_array[p];
				for(int p = 0; p < N; p++){
					if(i+p >= k-p)break;
					swap(work[i+p],work[k-p]);
				}

				next_number = 0;
				for(int p = 0; p < N; p++){
					next_number = 10*next_number + work[p];
				}

				auto at = MAP.find(next_number);

				if(at == MAP.end()){ //初登場の数字
					MAP[next_number] = swap_count+1;
				}else{
					if(next_number != sorted_num){
						continue; //queueで回しているから、先に登録された方が、必ず今回より等しい、または小さい
					}
				}

				if(next_number == sorted_num){ //答えが見つかったら、これ以上やらない(この分岐では、これ以上最適な解に辿り着かない)
					//なお、すぐ上でMAP内の存在確認を行っているため、ここに来たということは過去最少値
					//printf("next_num:%lld swap_count:%d\n",next_number,swap_count);
					ans = min(ans,swap_count+1);
				}else{
					if(swap_count <= 2){ //深さ4まで作る
						Q.push(Info(next_number,swap_count+1));
					}
				}
			}
		}
	}

	//ans側から、検索する
	Q.push(Info(sorted_num,0));
	rev_MAP[sorted_num] = 0;

	while(!Q.empty()){

		//数字を配列表現に直す
		tmp = Q.front().number;
		swap_count = Q.front().swap_count;
		Q.pop();

		if(swap_count+1 >= ans)continue;

		while(tmp > 0){
			S.push(tmp%10);
			tmp /= 10;
		}

		index = 0;
		while(!S.empty()){

			calc_array[index++] = S.top();
			S.pop();
		}

		if(index < N){ //先頭に0が(複数)来ている場合、0を補充する
			for(int i = index-1; i >=0; i--){
				calc_array[i+(N-index)] = calc_array[i];
			}
			for(int i = 0; i < N-index; i++){
				calc_array[i] = 0;
			}
		}

		for(int i = 0; i < N-1; i++){
			for(int k = i+1; k < N; k++){
				for(int p = 0; p < N; p++)work[p] = calc_array[p];
				for(int p = 0; p < N; p++){
					if(i+p >= k-p)break;
					swap(work[i+p],work[k-p]);
				}

				next_number = 0;
				for(int p = 0; p < N; p++){
					next_number = 10*next_number + work[p];
				}

				auto at = rev_MAP.find(next_number);
				if(at != rev_MAP.end())continue;	 //既に登場しているならSKIP
				rev_MAP[next_number] = swap_count+1;

				//first側とぶつかったか調べる
				at = MAP.find(next_number);

				if(at == MAP.end()){ //ぶつかっていない
					if(swap_count <= 3){ //4回までやる
						Q.push(Info(next_number,swap_count+1));
					}
				}else{ //ぶつかった場合
					ans = min(ans,swap_count+MAP[next_number]+1);
					//★ある状態から、firstへの距離が一気に2以上縮まることはない。よって、自分が1以上増えることにより、打ち切り★
				}
			}
		}
	}

	printf("%d\n",ans);

	return 0;
}