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 <algorithm>
#include <numeric>
#include <vector>
#include <cassert>
#include <string>
#include <memory.h>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <set>
#include <map>
#include <cctype>
#include <iomanip>
#include <sstream>
#include <cctype>
#include <fstream>
#include <cmath>
using namespace std;

#define REP2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define REP(i, n) REP2(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
#define ITER(c) __typeof((c).begin())
#define PB(e) push_back(e)
#define FOREACH(i, c) for(ITER(c) i = (c).begin(); i != (c).end(); ++i)
#define MP(a, b) make_pair(a, b)
#define PARITY(n) ((n) & 1)

typedef long long ll;
typedef pair<ll, ll> P;
const int INF = 1000 * 1000 * 1000 + 7;
const double EPS = 1e-10;

int best;
map<ll, int> memo;

ll encode(const vector<int> &x){
  ll H = 0;
  REP(i, x.size()) H = H * 11 + x[i];
  return H;
}

void dfs1(vector<int> &x, int depth){
  ll h = encode(x);
  if(memo.find(h) == memo.end() || memo[h] > depth){
    memo[h] = depth;
  }else{
    return;
  }
  if(depth == 4) return;

  REP(r, x.size())REP(l, r + 1){
    int d = (r - l + 1) / 2;
    REP(i, d) swap(x[l+i], x[r-i]);
    dfs1(x, depth + 1);
    REP(i, d) swap(x[l+i], x[r-i]);
  }
}

void dfs2(vector<int> &x, int depth){
  ll h = encode(x);
  if(memo.find(h) != memo.end()) best = min(best, memo[h] + depth);
  if(depth == 4) return;
  
  REP(r, x.size())REP(l, r + 1){
    int d = (r - l + 1) / 2;
    REP(i, d) swap(x[l+i], x[r-i]);
    dfs2(x, depth + 1);
    REP(i, d) swap(x[l+i], x[r-i]);
  }
}


int main(){
  int N;
  cin >> N;
  vector<int> x(N);
  vector<int> y(N);
  REP(i, N){
    cin >> x[i];
    y[i] = i + 1;
  }

  best = N - 1;
  dfs1(x, 0);
  dfs2(y, 0);
  cout << best << endl;
  return 0;
}