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]){
				first = 10*first+order[k];
			}
		}
	}

	sorted_num = 0;
	for(int i = 0; i < N; i++){
		sorted_num = 10*sorted_num+order[i];
	}

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

	MAP[sorted_num] = N-1;

	queue<Info> Q;

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

	Q.push(Info(first,0));

	ans = N-1;

	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){

			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 = MAP.find(next_number);

				if(at == MAP.end()){
					MAP[next_number] = swap_count+1;
				}else{
					if(next_number != sorted_num){
						continue;
					}
				}

				if(next_number == sorted_num){
					ans = min(ans,swap_count+1);
				}else{
					if(swap_count <= 2){
						Q.push(Info(next_number,swap_count+1));
					}
				}
			}
		}
	}

	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){
			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;
				rev_MAP[next_number] = swap_count+1;

				at = MAP.find(next_number);

				if(at == MAP.end()){
					if(swap_count <= 3){
						Q.push(Info(next_number,swap_count+1));
					}
				}else{
					ans = min(ans,swap_count+MAP[next_number]+1);
				}
			}
		}
	}

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

	return 0;
}