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<iostream>
#include<vector>
#include<unordered_map>
#include<queue>
#include<algorithm>

using namespace std;

struct S{
  char v[10];
  int size;
  int c,d,e;
  long long b;
  S(const vector<int> &pv,int pc):c(pc){
    size=pv.size();
    copy(begin(pv),end(pv),begin(v));
    eval();
  }
  void eval(){
    b=0;
    for(int i=0;i<size;i++){
      b=(b<<4)+v[i];
    }
    d=(v[0]!=1)+(v[size-1]!=size);
    for(int i=0;i+1<size;i++){
      d+=abs(v[i]-v[i+1])>1;
    }
    e=c+(d+1)/2;
  }    
  void reverse(int a,int b){
    c++;
    std::reverse(begin(v)+a,begin(v)+b+1);
    eval();
  }
  bool operator<(const S &s)const{
    return e>s.e;
  }
};

int main(){
  int N;
  cin>>N;
  vector<int> v(N);
  for(auto &e:v){
    cin>>e;
  }
  S is(v,0);
  priority_queue<S> que;
  que.push(is);
  unordered_map<long long,int> m;
  m[is.b]=0;
  for(;;){
    S c=que.top();
    if(c.d==0)break;
    que.pop();
    for(int i=0;i<N;i++){
      for(int j=i+1;j<N;j++){
	S n=c;
	n.reverse(i,j);
	if(m.count(n.b)&&m[n.b]<=n.c)continue;
	m[n.b]=n.c;
	que.push(n);
      }
    }
  }
  cout<<que.top().c<<endl;
}