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<map>
#include<queue>
 
#define cost first
#define state second
#define all(c) (c).begin(),(c).end()
 
using namespace std;
 
typedef pair<int,vector<int> > p2;
 
map<vector<int>,int> dist2;
 
int n;
queue<p2> que;

map<vector<int>,int> bfs(vector<int>start){
  
  map<vector<int>,int> dist;

  que.push(p2(0,start));
  dist[start]=0;
  while(!que.empty()){
    p2 now = que.front();
    que.pop();
    
    if(dist.find(now.state)!=dist.end() && dist[now.state]<now.cost)continue;
    if(now.cost>=(n-1)/2)continue;
     
    for(int i=0;i<n;i++){
      for(int j=i+1;j<n;j++){
	vector<int>t=now.state;
	reverse(t.begin()+i,t.begin()+j+1);
	if(dist.find(t)==dist.end()){
	  dist[t]=now.cost+1;
	  que.push(p2(now.cost+1,t));
	}
      }
    }
  }
  return dist;
}

int solve(vector<int> start){
  map<vector<int>,int>a,b;
  a=bfs(start);
  vector<int>goal=start;
  sort(all(goal));
  b=bfs(goal);

  int ans=start.size()-1;
  if(a.find(goal)!=a.end())ans = min(ans,a[goal]);

  do {
      if(a.find(goal) == a.end()) continue;
      if(b.find(goal) == b.end()) continue;
      ans = min(ans, a[goal] + b[goal]);
  } while(next_permutation(all(goal)));

  return ans;
}

int main(void){
 
  cin >> n;
 
  vector<int>v(n);
  for(int i=0;i<n;i++)cin >> v[i];
 
  cout << solve(v) << endl;
   
  return 0;
}