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;

long long swp(long long a, int i, int j) {
    long long t = ((a >> (i << 2)) ^ (a >> (j << 2))) & 15;
    return a ^ (t << (i << 2)) ^ (t << (j << 2));
}

int main() {
    int n;
    cin >> n;
    long long a = 0, m = 0;
    for (int i = 0; i < n; ++i) {
        int b;
        cin >> b;
        a = (a << 4) + b;
        m = (m << 4) + i + 1;
    }
    unordered_map<long long, int> mp;
    mp[m] = 0;
    queue<long long> q;
    q.push(m);

    int lim = 4;

    while (!q.empty()) {
        long long p = q.front();
        q.pop();
        if (mp[p] > lim) break;

        for (int i = 0; i < n; ++i) {
            long long pa = p;
            for (int j = 1; i + j < n && i - j >= 0; ++j) {
                pa = swp(pa, i - j, i + j);
                if (!mp.count(pa)) {
                    mp[pa] = mp[p] + 1;
                    q.push(pa);
                }
            }
            pa = p;
            for (int j = 0; i + j + 1 < n && i - j >= 0; ++j) {
                pa = swp(pa, i - j, i + j + 1);
                if (!mp.count(pa)) {
                    mp[pa] = mp[p] + 1;
                    q.push(pa);
                }
            }
        }
    }
    if (mp.count(a)) {
        cout << mp[a] << "\n";
        return 0;
    }
    unordered_map<long long, int> mp2;
    mp2[a] = 0;
    queue<long long> q2;
    q2.push(a);
    while (!q2.empty()) {
        long long p = q2.front();
        q2.pop();

        for (int i = 0; i < n; ++i) {
            long long pa = p;
            for (int j = 1; i + j < n && i - j >= 0; ++j) {
                pa = swp(pa, i - j, i + j);
                if (!mp2.count(pa)) {
                    mp2[pa] = mp2[p] + 1;
                    if (mp.count(pa)) {
                        cout << (mp[pa] + mp2[pa]) << "\n";
                        return 0;
                    }
                    q2.push(pa);
                }
            }
            pa = p;
            for (int j = 0; i + j + 1 < n && i - j >= 0; ++j) {
                pa = swp(pa, i - j, i + j + 1);
                if (!mp2.count(pa)) {
                    mp2[pa] = mp2[p] + 1;
                    if (mp.count(pa)) {
                        cout << (mp[pa] + mp2[pa]) << "\n";
                        return 0;
                    }
                    q2.push(pa);
                }
            }
        }
    }
    return 0;
}