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;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
int N;
int A[11];
string initial;
string goal;
set<string> st[2][6];
void bfs(int index, string &now) {
    st[index][0].insert(now);
    for(int cost = 0; cost < 4; cost++) {
        for(auto itr = st[index][cost].begin(); itr != st[index][cost].end(); itr++) {
            string nowst = *itr;
            for(int i = 0; i < nowst.size(); i++) {
                for(int j = i + 2; j <= nowst.size(); j++) {
                    reverse(nowst.begin() + i, nowst.begin() + j);
                    bool ok = true;
                    for(int k = 0; k <= cost + 1; k++) {
                        if(st[index][k].find(nowst) != st[index][k].end()) ok = false;
                    }
                    if(ok) {
                        st[index][cost+1].insert(nowst);
                        //cerr << index << " " << cost + 1 << " " << st[index][cost+1].size() << " " << nowst << endl;
                    }
                    reverse(nowst.begin() + i, nowst.begin() + j);
                }
            }
        }
    }
}

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    string start;
    for(int i = 1; i <= N; i++) {
        cin >> A[i];
        A[i]--;
        initial.push_back('0' + A[i]);
        start.push_back('0' + A[i]);
    }
    sort(start.begin(), start.end());
    bfs(0, start);
    //cerr << st[0][5].size() << endl;
    bfs(1, initial);
    int ans = 9;
    for(int i = 0; i <= 5; i++) {
        for(auto itr = st[0][i].begin(); itr != st[0][i].end(); itr++) {
            //cerr << i << " " << *itr << endl;
            for(int j = 0; j <= 5; j++) {
                if(st[1][j].find(*itr) != st[1][j].end()) ans = min(ans, i + j);
            }
        }
    }
    cout << ans << endl;
    return 0;
}