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 <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <numeric>
#include <queue>
#include <utility>
#include <iostream>
using namespace std;
using Map = map< vector<int>, int >;

int N;

vector<int> flip(vector<int> &vec, int &l, int &r) {
    vector<int> ret = vec;

    for(int i=l; i<=r; i++) {
        int il = i, ir = r - (i-l);
        if(il >= ir) break;

        swap(ret[il], ret[ir]);
    }
    return ret;
}

int solve(vector<int> &init, vector<int> &term, Map &cur, Map &pre) {
    int ret = N - 1;
    queue< vector<int> > que;
    que.push(init);

    while(que.size()) {
        vector<int> vec = que.front(); que.pop();
        if(pre.count(vec)) {
            ret = min(ret, cur[ vec ] + pre[ vec ]);
        }
        if(cur[ vec ] >= (N - 1) / 2) continue;

        for(int l=0; l<N; l++) {
            for(int r=l+1; r<N; r++) {
                vector<int> nxt = flip(vec, l, r);
                if(cur.count(nxt)) continue;
                cur[ nxt ] = cur[ vec ] + 1;
                que.push(nxt);
            }
        }
    }

    return ret;
}

int main() {
    scanf("%d", &N);
    vector<int> perm(N);
    for(int i=0; i<N; i++) {
        scanf("%d", &perm[i]);
    }

    vector<int> term(N);
    iota(term.begin(), term.end(), 1);

    Map ml, mr;
    ml[ perm ] = 0;
    mr[ term ] = 0;

    int ans = N - 1;
    ans = min(ans, solve(perm, term, ml, mr));
    ans = min(ans, solve(term, perm, mr, ml));
    printf("%d\n", ans);
    return 0;
}