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:
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

const i64 MOD = 1e9 + 7;
const i64 INF = i64(1e18) + 7;

template <typename T>
bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}


bool solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        --a[i];
    }

    map<vector<int>, int> range, v_range;
    vector<int> start(n);
    iota(start.begin(), start.end(), 0);

    queue<vector<int>> que;
    que.push(start);
    while(!que.empty()){
        auto pos = move(que.front());
        que.pop();
        int d = range[pos];
        for(int l = 0; l < n; ++l)
            for(int r = l + 2; r <= n; ++r){
                reverse(next(pos.begin(), l), next(pos.begin(), r));
                if(range.find(pos) == range.end()){
                    range[pos] = d + 1;
                    if(d + 1 < 4)
                        que.push(pos);
                }
                reverse(next(pos.begin(), l), next(pos.begin(), r));
            }
    }
    for(auto& p : range){
        vector<int> w(n);
        for(int i = 0; i < n; ++i)
            w[i] = a[p.first[i]];
        v_range[move(w)] = p.second;
    }
    int ans = 9;
    for(auto& p : range){
        if(v_range.find(p.first) == v_range.end())
            continue;
        chmin(ans, p.second + v_range[p.first]);
    }
    cout << ans << endl;

    return false;
}

signed main(){
    solve();
    return 0;
}