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;
typedef long long ll;
typedef pair<vector<int>,int> P;

int n, d, idx;

ll Vtoll(vector<int> V){
  
  ll res=0;
  
  for(int i=0;i<V.size();i++) res=res*10+V[i];
  
  return res;
  
}

map<ll,int> memo[2];

queue<P> q;

void bfs(vector<int> s){
  
  q.push(P(s,0));

  memo[idx][Vtoll(s)]=0;
  
  while(!q.empty()){

    P t=q.front(); q.pop();

    int cost=t.second;
    vector<int> S=t.first;
    
    if(cost==d) continue;
    
    for(int i=0;i<n-1;i++)
      for(int j=i+2;j<=n;j++){
	
	vector<int> nS=S;
	reverse(nS.begin()+i,nS.begin()+j);
	
	if(memo[idx].count(Vtoll(nS))) continue;
	memo[idx][Vtoll(nS)]=cost+1;
	
	q.push(P(nS,cost+1));
      }
    
  }
  
}

int main(){
  
  cin>>n;
  
  vector<int> A;
  
  A.resize(n);
  
  for(int i=0;i<n;i++) cin>>A[i],A[i]--;
  
  d=(n-1)/2;
  
  idx=0;
  
  bfs(A);
  
  d=(n-1)/2;
    
  idx=1;
  
  for(int i=0;i<n;i++) A[i]=i;
  
  bfs(A);

  int ans=n-1;
  
  map<ll,int>::iterator ite=memo[0].begin();

  while(ite!=memo[0].end()){
    
    if(memo[1].count((*ite).first))
      ans=min(ans,(*ite).second+memo[1][(*ite).first]);
    
    ite++;
    
  }
  
  cout<<ans<<endl;
  
  return 0;
}

/*

SAK

*/