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<bits/stdc++.h>
using namespace std;


int N;
vector<int> A;

bool check(vector<int>& a){
  for(int i=0;i<N;i++)
    if(a[i]!=i) return false;
  return true;
}
int ind(vector<int>&a, int x){
  for(int i=0;i<N;i++)
    if( a[i] == x ) return i;
}
void view(vector<int>& a){
  for(int i=0;i<N;i++) cout << a[i] << " ";
  cout << endl;
}

typedef pair<vector<int>,int> P;

void solve(map<vector<int>,int>& M,vector<int>& A){
  M.clear();
  queue<P> q;
  q.push( P(A, 0) );
  M[A] = 0;
  while( !q.empty() ){
    P p = q.front(); q.pop();
    if( p.second == 4 ) return;
    for(int i=0;i<N;i++){
      for(int j=i+1;j<N;j++){
        vector<int> a=p.first;
        reverse( a.begin()+i, a.begin()+j+1 );
        if( M.count( a ) == 0 ){
          M[a] = p.second+1;
          q.push( P(a,p.second+1) );
        }
      }
    }
  }
}

int main(){
  while(cin >> N){
    A.resize(N);
    for(int i=0;i<N;i++) {
      cin >>A[i]; A[i]--;
    }
    map<vector<int>,int> M1,M2;
    solve(M1,A);
    sort( A.begin(), A.end() );
    solve(M2,A);
    int res = 9;
    for( auto it = M1.begin(); it != M1.end();it++ )
      if( M2.count( it->first ) != 0 )
        res = min( res, it->second + M2[it->first] );
    cout << res << endl;
  }
}