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<bits/stdc++.h>
using namespace std;

int main(){

    int n; cin >> n;
    vector<int> a(n);
    vector<int> b(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) b[i] = i + 1;

    map<vector<int>, int> mb;
    queue<pair<vector<int>, int> > qb;
    
    mb[b] = -1;
    qb.push({b, 0});
    

    while(1){

        vector<int> now(n);
        now = qb.front().first;
        int cost = qb.front().second;
        qb.pop();
        
        if(cost == 4) break;

        bool ok = true;
        for(int i = 0; i < n; i++){
            if(a[i] != now[i]){
                ok = false;
                break;
            }
        }

        if(ok){
            cout << cost << endl;
            return 0;
        }

        for(int i = 0; i < n - 1; i++){
            for(int j = i + 1; j < n; j++){
                vector<int> next(n);
                next = now;

                for(int k = i; k <= j; k++){
                    next[k] = now[j - k + i];
                }


                if(mb.find(next) == mb.end()){
                    mb[next] = cost + 1;
                    qb.push({next, cost + 1});
                }
            }
        }
    }


    //cout << "junnbihadeketa" << endl;
    map<vector<int>, int> ma;
    queue<pair<vector<int>, int> > qa;
    ma[a] = -1;
    qa.push({a, 0});

    while(1){

        vector<int> now(n);
        now = qa.front().first;
        int cost = qa.front().second;
        qa.pop();

        if(cost == 4) break;

        if(mb.find(now) != mb.end()){
            cout << cost + mb[now] << endl;
            return 0;
        }

        for(int i = 0; i < n - 1; i++){
            for(int j = i + 1; j < n; j++){
                vector<int> next(n);
                next = now;
                for(int k = i; k <= j; k++){
                    next[k] = now[j + i - k];
                }

                if(ma.find(next) == ma.end()){
                    ma[next] == cost + 1;
                    qa.push({next, cost + 1});
                }
            }
        }
    }

    cout << 9 << endl;
    return 0;
}