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 <algorithm>
#include <queue>
#include <map>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <iostream>
typedef long long ll;

#include <set>
#include <cstdio>
inline int getInt(){ int s; scanf("%d", &s); return s; }

using namespace std;

struct state{
  ll v;
  state() : v(0){}
  state(const vector<int> &v) : v(0) { REP(i,v.size()) set(i, v[i]); }
  vector<int> decode(int n) const{
    vector<int> v(n); REP(i,n) v[i] = get(i);
    return v;
  }

  inline void set(int pos, int val){
    v &= ~(((1ll << ((pos + 1) * 4)) - 1) - ((1ll << (pos * 4)) - 1));
    v |= ((ll)val) << (pos * 4);
  }

  inline int get(int pos) const{
    return (v >> (pos * 4)) & ((1 << 4) - 1);
  }
};

map<ll, int> solve(int n, state s, map<ll, int> *prev = NULL){
  map<ll, int> ret;

  queue<state> q;
  ret[s.v] = 0; q.push(s);

  while(q.size()){
    const state st = q.front(); q.pop();
    const int cnt  = ret[st.v];

    if(prev != NULL && prev->count(st.v))
      throw (*prev)[st.v] + cnt;
    if(cnt == 4) continue;

    REP(i,n) REP(j,i){
      vector<int> v = st.decode(n);
      reverse(v.begin() + j, v.begin() + i + 1);
      const state next(v);
      if(ret.count(next.v) == 0){
        ret[next.v] = cnt + 1;
        q.push(next);
      }
    }
  }

  return ret;
}

int main(){
  const int n = getInt();
  state init;
  state goal;
  REP(i,n) init.set(i, getInt() - 1);
  REP(i,n) goal.set(i, i);

  if(init.v == goal.v){
    cout << 0 << endl;
  }else{
    map<ll, int> s1 = solve(n, init);
    try{
      map<ll, int> s2 = solve(n, goal, &s1);
      cout << 9 << endl;
    }catch(int e){
      cout << e << endl;
    }
  }
  return 0;
}