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 <map>
#include <queue>
#include <algorithm>
using namespace std;

int n;
string first, sorted;
map<int,int> closed, closed2;

int toInt(const string &s){
  int res = 0;

  for(int i = 1; i < n; i++){
    res *= 10;
    res += s[i] - '0';
  }

  return res;
}

typedef pair<string,int> P;

void bfs(){
  queue<P> open;
  open.push(P(first, 0));

  closed.clear();
  closed[toInt(first)] = 0;

  while(!open.empty()){
    P p = open.front(); open.pop();

    for(int from = 0; from < n - 1; from++){
      for(int to = from + 1; to < n; to++){
        string ns = p.first;
        reverse(ns.begin() + from, ns.begin() + to + 1);

        int x = toInt(ns);

        if(closed.find(x) == closed.end()){
          closed[x] = p.second + 1;

          if(p.second + 1 < 4){
            open.push(P(ns, p.second + 1));
          }
        }
      }
    }
  }
}

void solve(){
  int ans = n - 1;
  queue<P> open;
  open.push(P(sorted, 0));

  int x = toInt(sorted);

  closed2.clear();
  closed2[x] = 0;

  if(closed.find(x) != closed.end()){
    ans = min(ans, closed[x]);
  }

  while(!open.empty()){
    P p = open.front(); open.pop();

    for(int from = 0; from < n - 1; from++){
      for(int to = from + 1; to < n; to++){
        string ns = p.first;
        reverse(ns.begin() + from, ns.begin() + to + 1);

        int x = toInt(ns);

        if(closed.find(x) != closed.end()){
          ans = min(ans, p.second + closed[x] + 1);
        }
        else if(closed2.find(x) == closed2.end()){
          closed2[x] = p.second + 1;

          if(p.second + 1 < 4){
            open.push(P(ns, p.second + 1));
          }
        }
      }
    }
  }

  cout << ans << endl;
}

int main(){
  while(cin >> n){
    first = "";
    sorted = "";

    for(int i = 0; i < n; i++){
      int x;
      cin >> x;
      first += '0' + (char)(x - 1);
      sorted += '0' + (char)i;
    }

    bfs();
    solve();
  }
}