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;

constexpr int INF = numeric_limits<int>::max() / 2;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N;
    cin >> N;
    vector<int> a(N), gt(N);
    for (int i = 0; i < N; i++)
    {
        cin >> a[i];
        gt[i] = i + 1;
    }
    map<vector<int>, int> dist, rdist;
    queue<vector<int>> que;
    dist[a] = 0;
    que.push(a);
    while (!que.empty())
    {
        auto v = que.front();
        que.pop();
        if (dist[v] >= 4)
            continue;
        /*
        int sx = 0, gx = N - 1;
        while (v[sx] == sx + 1)
            sx++;
        while (v[gx] == gx + 1)
            gx--;
        */
        for (int i = 0; i < N; i++)
        {
            for (int j = i + 1; j < N; j++)
            {
                auto v2 = v;
                reverse(v2.begin() + i, v2.begin() + j + 1);
                if (dist.find(v2) != dist.end())
                    continue;
                dist[v2] = dist[v] + 1;
                que.push(v2);
            }
        }
    }
    rdist[gt] = 0;
    que.push(gt);
    while (!que.empty())
    {
        auto v = que.front();
        que.pop();
        if (rdist[v] >= 4)
            continue;
        /*
        int sx = 0, gx = N - 1;
        while (v[sx] == sx + 1)
            sx++;
        while (v[gx] == gx + 1)
            gx--;
        */
        for (int i = 0; i < N; i++)
        {
            for (int j = i + 1; j < N; j++)
            {
                auto v2 = v;
                reverse(v2.begin() + i, v2.begin() + j + 1);
                if (rdist.find(v2) != rdist.end())
                    continue;
                rdist[v2] = rdist[v] + 1;
                que.push(v2);
            }
        }
    }
    int ret = 9;
    for (const auto &v : dist)
    {
        if (rdist.find(v.first) != rdist.end())
            ret = min(ret, dist[v.first] + rdist[v.first]);
    }
    cout << ret << endl;
}