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 <sstream>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstdio>
#include <numeric>
#include <bitset>
#include <stack>
#include <cstring>
using namespace std;

const int INF = 1 << 30;
const double EPS = 1e-10;

vector<int> reverse(int l, int r, const vector<int>& A)
{
  vector<int> ret = A;
  for (int i = 0; i <= (r-l)/2; ++i)
    swap(ret[l+i], ret[r-i]);
  return ret;
}

void solve(const int N, const vector<int>& v, map<vector<int>, int>& dp)
{
  queue<vector<int> > que;
  que.push(v);
  dp[v] = 0;
  for (int i = 0; i < 4; ++i) {
    queue<vector<int> > next;
    while (!que.empty()) {
      const vector<int> q = que.front();
      que.pop();
      
      for (int j = 0; j < N; ++j) {
        for (int k = j+1; k < N; ++k) {
          vector<int> qq = reverse(j, k, q);
          if (dp.find(qq) == dp.end()) {
            dp[qq] = i+1;
            next.push(qq);
          }
        }
      }
    }
    swap(que, next);
  }
}

int main()
{
  int N;
  while (cin >> N) {
    vector<int> A(N);
    for (int i = 0; i < N; ++i)
      cin >> A[i];

    map<vector<int>, int> sdp, rdp;
    solve(N, A, sdp);
    sort(A.begin(), A.end());
    solve(N, A, rdp);

    int ans = N-1;
    for (map<vector<int>, int>::iterator it = sdp.begin(); it != sdp.end(); ++it) {
      if (rdp.find(it->first) != rdp.end())
        ans = min(ans, it->second+rdp[it->first]);
    }
    cout << ans << endl;
  }
  return 0;
}