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>

#define REP(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;

int frac[11];

int to_i(const vector<int> &v) {
  int n = v.size();
  vector<bool> used(n, false);
  int index = 0;
  REP(i,n) {
    for(int j=v[i]-1; j>=0; --j)
      if (!used[j])
        index += frac[n-i-1];
    used[v[i]] = true;
  }
  return index;
}

vector<int> to_p(int index, int n) {
  vector<bool> used(n, false);
  vector<int> perm(n);
  REP(i,n) {
    REP(j,n) {
      if(used[j]) continue;
      if(frac[n-i-1] <= index) index -= frac[n-i-1];
      else {
        perm[i] = j;
        used[j] = true;
        break;
      }
    }
  }
  return perm;
}

void out(const vector<int>& s) {
  for(int v:s)cout<<v<<' ';
  cout<<endl;
}

map<int, int> getm(const vector<int>& s) {
  int n = s.size();
  map<int,int> ms;
  queue<tuple<int,int>> qs;
  ms[to_i(s)] = 0;
  qs.push(make_tuple(0, to_i(s)));
  while(!qs.empty()) {
    int d, i;
    tie(d, i) = qs.front(); qs.pop();
    if (ms[i] < d) continue;
    if (d >= 4) break;
    auto v = to_p(i, n);
    REP(j,n+1) REP(k,j-1) {
      auto cp = v;
      reverse(begin(cp)+k,begin(cp)+j);
      int ni = to_i(cp);
      if (ms.find(ni) == end(ms) || ms[ni] > ms[i]) {
        ms[ni] = ms[i] + 1;
        qs.push(make_tuple(ms[ni], ni));
      }
    }
  }
  return ms;
}

int main() {
  frac[0] = 1;
  REP(i,10) frac[i+1] = frac[i] * (i+1);
  int n;
  cin>>n;
  vector<int> s(n), t(n);
  REP(i,n) {
    cin>>s[i];
    --s[i];
  }
  iota(begin(t),end(t),0);
  auto ms = getm(s);
  auto mt = getm(t);
  int mn = n-1;
  for(auto p:ms){
    int i,d;
    tie(i,d) = p;
    auto itr = mt.find(i);
    if(itr != end(mt)) {
      mn = min(mn, d + itr->second);
    }
  }
  cout << mn << endl;
  return 0;
}