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<algorithm>
#include<queue>
#include<map>
using namespace std;

typedef pair< int, vector<int> > P;
#define DEPTH first
#define ARRAY second

int main(){
  int ans;
  int N;
  cin>>N;
  vector<int> A(N), sorted(N);
  for(int i=0; i<N; i++){
    cin>>A[i];
    sorted[i]=i+1;
  }

  map< vector<int>, int > num;
  queue<P> q;
  q.push( P(0,sorted) );
  while(!q.empty()){
    P now=q.front();
    q.pop();
    if(now.DEPTH>=4)break;
    if(num.count(now.ARRAY))continue;
    num[now.ARRAY] = now.DEPTH;
    for(int i=0; i<N; i++){
      for(int j=i+1; j<N; j++){
        P next=now;
        next.DEPTH++;
        reverse(next.ARRAY.begin()+i,next.ARRAY.begin()+j+1);
        q.push(next);
      }
    }
  }

  map< vector<int>, int > num2;
  queue<P> q2;
  q2.push( P(0,A) );
  while(!q2.empty()){
    P now=q2.front();
    q2.pop();
    if(now.DEPTH>=4)break;
    if(num2.count(now.ARRAY))continue;
    num2[now.ARRAY] = now.DEPTH;
    for(int i=0; i<N; i++){
      for(int j=i+1; j<N; j++){
        P next=now;
        next.DEPTH++;
        reverse(next.ARRAY.begin()+i,next.ARRAY.begin()+j+1);
        q2.push(next);
      }
    }
  }

  ans=9;
  map< vector<int>, int >::iterator it;;
  for(it=num.begin(); it!=num.end(); it++){
    if(!num2.count(it->first))continue;
    ans = min(ans, it->second + num2[it->first]);
  }

  cout<<ans<<endl;
}