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 int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vii;
#define rrep(i, m, n) for(int (i)=(m); (i)<(n);  (i)++)
#define erep(i, m, n) for(int (i)=(m); (i)<=(n); (i)++)
#define  rep(i, n)    for(int (i)=0; (i)<(n);  (i)++)
#define rrev(i, m, n) for(int (i)=(n)-1; (i)>=(m); (i)--)
#define erev(i, m, n) for(int (i)=(n); (i)>=(m); (i)--)
#define  rev(i, n)    for(int (i)=(n)-1; (i)>=0; (i)--)
#define vrep(i, c)    for(__typeof((c).begin())i=(c).begin(); i!=(c).end(); i++)
#define  ALL(v)       (v).begin(), (v).end()
#define pb            push_back
#define mp            make_pair
template<class T, class S> inline bool minup(T& m, const S x){ return m>(T)x ? (m=(T)x, true) : false; }
template<class T, class S> inline bool maxup(T& m, const S x){ return m<(T)x ? (m=(T)x, true) : false; }

static const int    INF = 1000000000;
static const ll     MOD = 1000000007LL;
static const double EPS = 1E-10;

template<typename T> ostream& operator <<(ostream& r, const vector<T> t){vrep(v,t)r<<*v<<(v+1==t.end()?"":" ");return r;}
template<typename T> ostream& operator <<(ostream& r, const pair<vector<T>, int> p){int n=p.second;minup(n,p.first.size());rep(i,n-1)r<<p.first[i]<<' ';r<<p.first[n-1];return r;}
template<typename T> ostream& operator <<(ostream& r, const pair<T*, int> p){int n=p.second-1;rep(i,n)r<<p.first[i]<<' ';return r<<p.first[n];}
template<typename T, size_t S> ostream& operator <<(ostream& r, const T (&a)[S]){rep(i,S-1)r<<a[i]<<' ';return r<<a[S-1];}


int N;
map<vi, int> d[2];
queue<pair<vi, int> > que[2];

int main(int argc, char *argv[])
{
  cin >> N;
  vi A(N), S(N);
  rep(i, N) cin >> A[i];
  S = A;
  sort(ALL(S));

  d[0][A] = 0;
  que[0].push(mp(A, 0));
  while(!que[0].empty()){
    vi top = que[0].front().first;
    int cost = que[0].front().second;
    que[0].pop();
    if(top == S){
      cout << cost << endl;
      return 0;
    }
    if(cost >= 4) break;
    rep(j, N) rep(i, j){
      vi t = top;
      reverse(t.begin() + i, t.begin() + j + 1);
      if(t != A && !d[0][t]){
        d[0][t] = cost + 1;
        que[0].push(mp(t, cost + 1));
      }
    }
  }
  
  d[1][S] = 0;
  que[1].push(mp(S, 0));
  while(!que[1].empty()){
    vi top = que[1].front().first;
    int cost = que[1].front().second;
    que[1].pop();
    if(d[0][top]){
      cout << cost + d[0][top] << endl;
      return 0;
    }
    if(cost >= 4) break;
    rep(j, N) rep(i, j){
      vi t = top;
      reverse(t.begin() + i, t.begin() + j + 1);
      if(!d[1][t]){
        d[1][t] = cost + 1;
        que[1].push(mp(t, cost + 1));
      }
    }
  }

  cout << N - 1 << endl;
  
  return 0;
}