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 <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <cmath>
#include <fstream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <iterator>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <stack>
#include <climits>
#include <deque>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
double EPS=1e-10;
double EQ(double a,double b){
    return abs(a-b)<EPS;
}
void fast_stream(){
  std::ios_base::sync_with_stdio(0);
}
template<class T>
string IntToString(T num){
  string res;stringstream ss;ss<<num;
  return ss.str();
}
ll StringToInt(string &str){
  ll res=0;
  for(int i=0;i<(int)str.size();i++)
    res=(res*10+str[i]-'0');
  return res;
}

vector<char> v;
map<vector<char> ,int> d1;
map<vector<char> ,int> d2;
int N;
vector<char> sorted;

int main(){
  cin>>N;
  for(int i=0;i<N;i++){
    int a;
    cin>>a;
    v.push_back(a);
  }
  sorted=v;
  sort(v.begin(),v.end());
  queue<vector<char> > q1,q2;
  d1[v]=0;
  d2[sorted]=0;
  q1.push(v);
  q2.push(sorted);
  int ans=1<<30;
  while(q1.size()||q2.size()){
    {
      vector<char> now=q1.front();q1.pop();
      int ccost=d1[now];
      if(now==sorted){
	cout<<ccost<<endl;
	return 0;
      }
      for(int i=0;i<N;i++){
	for(int j=i+1;j<N;j++){
	  vector<char> nv=now;
	  reverse(nv.begin()+i,nv.begin()+j+1);
	  if(d2.count(nv)!=0&&d1.count(nv)==0)
	    ans=min(ans,ccost+1+d2[nv]);
	  else if(d1.count(nv)==0){
	    d1[nv]=ccost+1;
	    q1.push(nv);
	  }
	}
      }
    }
    {
      vector<char> now=q2.front();q2.pop();
      int ccost=d2[now];
      if(v==now){
	cout<<ccost<<endl;
	return 0;
      }
      for(int i=0;i<N;i++){
	for(int j=i+1;j<N;j++){
	  vector<char> nv=now;
	  reverse(nv.begin()+i,nv.begin()+j+1);
	  if(d1.count(nv)!=0&&d2.count(nv)==0)
	    ans=min(ans,ccost+1+d1[nv]);
	  else if(d2.count(nv)==0){
	    d2[nv]=ccost+1;
	    q2.push(nv);
	  }
	}
      }
    }
    if(q1.size()&&q2.size()){
      int sum=d1[q1.front()]+d2[q2.front()]+1;
      if(sum>=ans)break;
    }
  }
  cout<<ans<<endl;

  return 0;
}