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 <queue>
#include <algorithm>
#include <vector>
#include <map>

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;
    }

    map<vector<int>, int> d, h;
    int ans = N - 1;

    // from goal
    {
        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);
                    }
                }
        }
    }

    // from start
    {
        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;

    return 0;
}