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 <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctype.h>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define lengthof(x) (sizeof(x) / sizeof(*(x)))
#define FILL(ptr, value) FILL_((ptr), sizeof(ptr)/sizeof(value), (value))
template <typename T>
void FILL_(void * ptr, size_t size, T value){
  std::fill((T*)ptr, (T*)ptr+size, value);
}
//参照http://www27.atpages.jp/tasuku/pro/3_algo.pdf 

//4方向ベクトル→↑←↓
int dx[] ={1,0,-1,0};
int dy[] ={0,-1,0,1};

int main()
{
  int n;
  cin >>n;
  int ans=n;
  vector<int> a(n),b(n);//スタート、ゴールから
  for(int i = 0;i < n;i++){
    cin>>a[i];
    b[i] = i+1;
  }//d[v] =スタートからの距離,h[v]=ゴールからの距離
  map<vector<int>,int> d,h;
  //解は最大でもn-1;
  //ゴールから探索
  {
    h[b] = 0;
    queue<vector<int> > q;
    q.push(b);
    while(!q.empty()){
      vector<int> v = q.front();
      int cost = h[v];
      q.pop();
      if(v ==a){//一致するなら
	ans = cost;
	break;
      }
      if(cost >=4)
	break;
      for(int i = 0;i < n;i++){
	for(int j = i+1;j < n;j++){
	  vector<int> next = v;
	  reverse(next.begin()+i,next.begin()+j+1);
	  if(!h.count(next)){//まだ無ければ追加
	    h[next] = cost+1;
	    q.push(next);
	  }
	}
      }
    }
  }
    //スタートからの探索
    {
      d[a] = 0;
      queue<vector<int> > q;
      q.push(a);
      while(!q.empty()){
	vector<int> v = q.front();
	int cost = d[v];
	q.pop();
	if(h.count(v)){
	  ans = cost + h[v];
	  break;
	}
	if(cost >=4){
	  break;
	}
	for(int i = 0;i < n;i++){
	  for(int j = i+1;j < n;j++){
	    vector<int> next = v;
	    reverse(next.begin()+i, next.begin()+j+1);
	    if(!d.count(next)){
	      d[next] = cost +1;
	      q.push(next);
	    }
	  }
	}
      }
    }
    if(ans ==n){
      ans =n-1;
    }
    cout <<ans<<endl;
    return 0;
}