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 <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

int n;
const ull BASE = 1e+9+7;
map<ull, int> open[2];

ull getHash(const vector<char> &seq) {
  ull ret = 0;
  REP(i, n) {
    ret = ret * BASE + seq[i];
  }
  return ret;
}

int main() {
  while (scanf("%d", &n) > 0) {
    open[0].clear();
    open[1].clear();
    vector<char> ini;
    REP(i, n) {
      int v;
      scanf("%d", &v);
      v--;
      ini.push_back(v);
    }
    queue<pair<vector<char>, char> > que;
    open[0][getHash(ini)] = 0;
    que.push(make_pair(ini, 0));
    {
      vector<char> sorted(n);
      REP(i, n) {
        sorted[i] = i;
      }
      open[1][getHash(sorted)] = 0;
      if (ini == sorted) {
        printf("0\n");
        continue;
      }
      que.push(make_pair(sorted, 1));
    }
    while (!que.empty()) {
      vector<char> seq = que.front().first;
      int lr = que.front().second;
      int ncost = open[lr][getHash(seq)] + 1;
      que.pop();
      REP(i, n) {
        FOR(j, i + 1, n) {
          vector<char> nseq = seq;
          reverse(nseq.begin() + i, nseq.begin() + j + 1);
          ull h = getHash(nseq);
          if (open[lr].count(h)) { continue; }
          if (open[lr ^ 1].count(h)) {
            printf("%d\n", ncost + open[lr ^ 1][h]);
            goto next;
          }
          open[lr][h] = ncost;
          que.push(make_pair(nseq, lr));
        }
      }
    }
    assert(false);
next:;
  }
}