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 <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 10

/* Permutation <-> ID */
// {0,1,2} <=> 0, {0,2,1} <=> 1, {2, 1, 0} <=> 5

namespace PermutationConverter {
  const int MAX_DATASIZE = 20;

  ll encode(int N, const int *data){
    bool used[MAX_DATASIZE] = {};
    ll id = 0, t = 1;

    for(int i=1; i<=N; i++) t *= i;

    for(int i=0; i<N; i++){
      t /= (N - i);
      used[data[i]] = true;
      id += count(used, used+data[i], false) * t;
    }

    return id;
  }

  void decode(int N, ll id, int *data) {
    bool used[MAX_DATASIZE] = {};
    ll t = 1;

    for(int i=1; i<=N; i++) t *= i;

    for(int i=0; i<N; i++) {
      t /= (N - i);

      int s = id / t;
      for(int j=0; ; j++) {
        if (!used[j] && s == 0) {
          data[i] = j;
          used[j] = true;
          break;
        }
        s -= !used[j];
      }

      id %= t;
    }
  }
};

void bfs(int N, int *A, map<int, int> &ss) {

  queue<int> que1, que2;

  que1.push(PermutationConverter::encode(N, A));

  for(int i=0; i<4; i++) {

    while(que1.size()) {
      int id = que1.front();
      que1.pop();

      if (ss.find(id) != ss.end()) continue;
      ss[id] = i;

      PermutationConverter::decode(N, id, A);

      for (int i=0; i<N; i++) {
        for (int j=i+2; j<=N; j++) {
          reverse(A+i, A+j);
          que2.push(PermutationConverter::encode(N, A));
          reverse(A+i, A+j);
        }
      }
    }

    swap(que1, que2);
  }
}

int main(){
  int N, A[SIZE], B[SIZE];

  scanf("%d", &N);

  for (int i=0; i<N; i++) {
    scanf("%d", A+i);
    A[i]--;
  }

  iota(B, B+N, 0);

  map<int, int> ss1, ss2;

  bfs(N, A, ss1);
  bfs(N, B, ss2);

  int ans = N-1;

  for (auto p : ss2) {
    auto it = ss1.find(p.first);
    if (it == ss1.end()) continue;
    ans = min(ans, p.second + it->second);
  }

  cout << ans << endl;

  return 0;
}