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 <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <ctime>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <iterator>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) container.begin(), container.end()
#define RALL(container) container.rbegin(), container.rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}

const int INF = 1<<28;
const double EPS = 1e-8;
const int MOD = 1000000007;


int n;

ull PermutationHash(vi perm){
	static ull FACTOR[21]={0};
	if(FACTOR[0] == 0){
		FACTOR[0] = 1;
		REP(i, 20) FACTOR[i+1] = FACTOR[i]*(i+1);
	}
	ull hash = 0;
    REP(i, (int)perm.size()-1) perm[i] = perm[i];
    REP(i, (int)perm.size()-1){
        hash += perm[i] * FACTOR[perm.size()-i-1];
        for (int j=i+1; j < (int)perm.size()-1; j++)
            if (perm[i] < perm[j]) perm[j]--;
    }
    return hash;
}

vi restorePermutation(ull u){
	static ull FACTOR[21]={0};
	if(FACTOR[0] == 0){
		FACTOR[0] = 1;
		REP(i, 20) FACTOR[i+1] = FACTOR[i]*(i+1);
	}
	vi res;
	RREP(i, n){
		int p = u/FACTOR[i];
		u%=FACTOR[i];
		res.push_back(p);
	}
	RREP(i, res.size())RREP(j, i) if(res[j] <= res[i]) res[i]++;
	return res;
}

int memo[3628801];
int rev[3628801];
int main(){
	while(cin >> n){
		memset(rev, 63, sizeof(memo));
		memset(memo, 63, sizeof(memo));
		vi a(n);
		REP(i, n) a[i] = i;
		queue< pair<int, ull> > pq;
		pq.emplace(0, 0);
		rev[0] = 0;
		while(!pq.empty()){
			int c = pq.front().first;
			ull u = pq.front().second;
			pq.pop();
			if(c > 3) break;
			vi a = restorePermutation(u);
			REP(i, n+1)REP(j, i){
				vi b(a);
				reverse(b.begin()+j, b.begin()+i);
				ull u = PermutationHash(b);
				if(chmin(rev[u], c+1)) pq.emplace(c+1, u);
			}
		}
		{
			memset(memo, 63, sizeof(memo));
			vi a(n);
			REP(i, n) cin >> a[i],a[i]--;
			queue< pair<int, ull> > pq;
			pq.emplace(0, PermutationHash(a));
			memo[PermutationHash(a)] = 0;
			int ans = n-1;
			while(!pq.empty()){
				int c = pq.front().first;
				ull u = pq.front().second;
				pq.pop();
				if(c > 3) break;
				ans = min(ans, c + rev[u]);
				vi a = restorePermutation(u);
				REP(i, n+1)REP(j, i){
					vi b(a);
					reverse(b.begin()+j, b.begin()+i);
					ull u = PermutationHash(b);
					if(chmin(memo[u], c+1)) pq.emplace(c+1, u);
					ans = min(ans, c + 1 + rev[u]);
				}
			}
			cout << ans << endl;
		}
	}
	return 0;
}