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

int main(){
    int n;
    cin >> n;
    
    vector<int> a(n), b(n);
    for(int i=0 ; i < n ; i++ ){
        cin >> a[i];
        b[i] = i+1;
    }
    // d[v] := スタートからの距離, h[v] := ゴールからの距離
    map<vector<int>,int> d, h;
    // 解は最大でも n-1 
    int ans = n-1;
    // ゴールから探索
    {
        h[b] = 0;
        queue<vector<int> > q;
        q.push( b );
        while( !q.empty() ){
            vector<int> v = q.front();
            int cost = h[v];
            q.pop();
            
            if( v == a ){
                ans = cost;
                break;
            }
            if( cost >= 4 ) break;
            
            for(int i=0 ; i < n ; i++ ){
                for(int j=i+1 ; j < n ; j++ ){
                    vector<int> next = v;
                    reverse( next.begin()+i , next.begin()+j+1 );
                    if( !h.count(next) ){
                        h[next] = cost+1;
                        q.push(next);
                    }
                }
            }
        }
    }
    // スタートから探索
    {
        d[a] = 0;
        queue<vector<int> > q;
        q.push( a );
        while( !q.empty() ){
            vector<int> v = q.front();
            int cost = d[v];
            q.pop();
            
            if( h.count(v) ){
                ans = cost + h[v];
                break;
            }
            if( cost >= 4 ) break;
            
            for(int i=0 ; i < n ; i++ ){
                for(int j=i+1 ; j < n ; j++ ){
                    vector<int> next = v;
                    reverse( next.begin()+i , next.begin()+j+1 );
                    if( !d.count(next) ){
                        d[next] = cost+1;
                        q.push(next);
                    }
                }
            }
        }
    }
    cout << ans << endl;
}