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 n;
long long int pool[3628800];
int fwd_min[3628800], bwd_min[3628800];
int fac[11];

long long int enc(int *p)
{
    long long int tmp = 0;
    for (int i = 0; i < n; i++){
        tmp = tmp * 10 + p[i] - 1;
    }
    return (tmp);
}

void bfs(int *p, int *s)
{
    for (int i = 0; i < fac[n]; i++){
        p[i] = -1;
    }

    int id = lower_bound(pool, pool + fac[n], enc(s)) - pool;
    int c[10];

    queue<int> q;
    q.push(id);

    p[id] = 0;

    while (q.size()){
        int x = q.front(); q.pop();

        long long int t = pool[x];
        for (int i = 0; i < n; i++){
            c[n - i - 1] = (t + 1) % 10;
            if (c[n - i - 1] == 0) c[n - i - 1] = 10;
            t /= 10;
        }

        for (int i = 0; i < n; i++){
            for (int j = i + 1; j < n; j++){
                int s = i, t = j;
                while (s < t){
                    c[s] ^= c[t]; c[t] ^= c[s]; c[s] ^= c[t];
                    s++; t--;
                }
                int y = lower_bound(pool, pool + fac[n], enc(c)) - pool;
                if (p[y] == -1){
                    p[y] = p[x] + 1;
                    if (p[y] < 4) q.push(y);
                }

                s = i, t = j;
                while (s < t){
                    c[s] ^= c[t]; c[t] ^= c[s]; c[s] ^= c[t];
                    s++; t--;
                }
            }
        }
    }
}

int main()
{
    int a[16], e[16];

    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    for (int i = 0; i < n; i++) e[i] = i + 1;

    int ctr = 0;
    do {
        long long int tmp = 0;
        for (int i = 0; i < n; i++){
            tmp = tmp * 10 + e[i] - 1;
        }
        pool[ctr++] = tmp;
    } while (next_permutation(e, e + n));

    sort(pool, pool + fac[n]);


    fac[0] = 1;

    for (int i = 1; i <= n; i++){
        fac[i] = i * fac[i - 1];
        e[i - 1] = i;
    }

    bfs(fwd_min, e);
    bfs(bwd_min, a);

    int ans = n - 1;
    int t = lower_bound(pool, pool + fac[n], enc(a)) - pool;

    if (~fwd_min[t]) ans = fwd_min[t];

    for (int i = 0; i < fac[n]; i++){
        if (~fwd_min[i] && ~bwd_min[i]) ans = min(ans, fwd_min[i] + bwd_min[i]);
    }

    printf("%d\n", ans);

    return (0);
}