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>
#define range(i, a, n) for(int (i) = (a); (i) < (n); (i)++)
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
using namespace std;
map<vector<int>, int> memo[2];
int main(void){
    int n; cin >> n;

    vector<int> a(n);
    for(auto & e : a) cin >> e;

    int nn = (n - 1) / 2;

    int res = n - 1;
    rep(i, 2){
        queue<vector<int>> q;
        q.push(a);
        memo[i][a] = 0;

        while(q.size()){
            vector<int> b;
            b = q.front(); q.pop();

            if(i == 1 and memo[0].find(b) != end(memo[0])){
                res = min(res, memo[0][b] + memo[1][b]);
                continue;
            }

            if(memo[i][b] >= nn) continue;

            rep(j, n){
                range(k, j + 1, n){
                    vector<int> nb = b;
                    reverse(begin(nb) + j, begin(nb) + k + 1);

                    if(memo[i].find(nb) != end(memo[i])) continue;

                    memo[i][nb] = memo[i][b] + 1;
                    q.push(nb);
                }
            }
        }

        sort(begin(a), end(a));
    }

    cout << res << endl;

	return 0;
}