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<map>
#include<vector>
#include<algorithm>
#include<cassert>
#include<queue>
#include<cstdio>
#include<ctime>
#include<climits>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29)

using namespace std;

struct P
{
  vector<int> A;
  int cost;
  P(vector<int> A2=vector<int>(),int cost=inf):cost(cost)
  {
    A = A2;
  }

  bool operator < (const P& a)const
  {
    return cost > a.cost;
  }

};

int N;
map<vector<int>,int> mincost;
map<vector<int>,int> rmincost;
vector<int> initial;
bool found;

void computeR(int step)
{
  priority_queue<P> Q;
  {
    initial.resize(N);
    rep(i,N)initial[i] = i+1;
    Q.push(P(initial,0));
    rmincost[initial] = 0;
  }

  //clock_t st,ed;
  //st = clock();
  while(!Q.empty())
    {
      P p = Q.top(); Q.pop();
      if(p.cost >= step)continue;

      //ed = clock();
      //if((double)(ed-st)/(double)CLOCKS_PER_SEC >= 1.0)return;      

      rep(s,N)
	{
	  REP(t,s+2,N+1)
	    {
	      vector<int> next = p.A;
	      reverse(next.begin()+s,next.begin()+t);
	      if(rmincost.find(next) == rmincost.end())
		{
		  rmincost[next] = p.cost + 1;
		  Q.push(P(next,p.cost+1));
		}
	    }
	}

    }
}

void compute(vector<int> &vec)
{
  mincost[vec] = 0;
  priority_queue<P> Q;
  Q.push(P(vec,0));

  int ans = inf;
  found = false;
  while(!Q.empty())
    {
      P p = Q.top(); Q.pop();

      //if(p.cost >= ans)continue;


      if(rmincost.find(p.A) != rmincost.end())
	{
	  found = true;
	  cout << p.cost + rmincost[p.A] << endl;
	  return;
	  //ans = min(ans,p.cost + rmincost[p.A]);
	  continue;
	}

      if(p.cost >= 4)continue;

      rep(s,N)
	{
	  REP(t,s+2,N+1)
	    {
	      vector<int> next = p.A;
	      reverse(next.begin()+s,next.begin()+t);
	      if(mincost.find(next) == mincost.end())
		{
		  mincost[next] = p.cost + 1;
		  Q.push(P(next,p.cost+1));
		}
	    }
	}
    }
  found = true;
  cout << N-1 << endl;
}

int main()
{

  int a = scanf("%d",&N);
  
  computeR(4);
  //cout << "---------" << endl;
  vector<int> vec(N);
  rep(i,N)a = scanf("%d",&vec[i]);

  compute(vec);


  return 0;
}