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 <algorithm>
#include <numeric>
#include <map>
#include <queue>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
template <class T> void setmin(T & a, T const & b) { if (b < a) a = b; }
void bfs(vector<int> xs, map<vector<int>,int> & memo) {
    int n = xs.size();
    queue<vector<int> > que;
    que.emplace(xs);
    while (not que.empty()) {
        vector<int> xs = que.front(); que.pop();
        int depth = memo[xs];
        repeat (r,n+1) repeat (l,r-1) {
            reverse(xs.begin() + l, xs.begin() + r);
            if (not memo.count(xs)) {
                memo[xs] = depth + 1;
                if (depth+1 < (n-1)/2) {
                    que.emplace(xs);
                }
            }
            reverse(xs.begin() + l, xs.begin() + r);
        }
    }
};
int main() {
    // input
    int n; scanf("%d", &n);
    vector<int> a(n);
    repeat (i,n) {
        scanf("%d", &a[i]);
        -- a[i];
    }
    // compute
    map<vector<int>,int> memo_l, memo_r;
    vector<int> b(n); iota(b.begin(), b.end(), 0);
    bfs(b, memo_l);
    bfs(a, memo_r);
    int ans = n-1;
    do {
        if (memo_l.count(b) and memo_r.count(b)) {
            setmin(ans, memo_l[b] + memo_r[b]);
        }
    } while (next_permutation(b.begin(), b.end()));
    // output
    printf("%d\n", ans);
    return 0;
}