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;

#define DUMP(x) cerr << #x << "=" << x << endl
#define DUMP2(x, y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<")"<< endl
#define BINARY(x) static_cast<bitset<16> >(x)

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for (int i=m;i<(int)(n);i++)

#define in_range(x, y, w, h) (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))
#define ALL(a) (a).begin(),(a).end()

typedef long long ll;
const int INF   = 1e9;
const ll  INFLL = 1e18;
typedef pair<int, int> PII;
int dx[4]={0, -1, 1, 0}, dy[4]={-1, 0, 0, 1};

int N;
map<vector<int>, int> vis;
int ans;

void dfs(int d, vector<int> &A, bool first)
{
    if (first) {
        if (!vis.count(A) || d < vis[A]) vis[A] = d;
    } else {
        if (vis.count(A)) ans = min(ans, d + vis[A]);
    }
    if (d == 4) return;

    for (int i=0; i<N; i++) {
        for (int j=i+1; j<N; j++) {
            reverse(A.begin() + i, A.begin() + j + 1);
            dfs(d+1, A, first);
            reverse(A.begin() + i, A.begin() + j + 1);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);

    cin >> N;
    vector<int> A(N);
    rep(i, N) cin >> A[i];
    ans = N-1;
    dfs(0, A, true);
    vector<int> B(N); iota(B.begin(), B.end(), 1);
    dfs(0, B, false);
    cout << ans << endl;

#ifdef DEBUG
    cerr << vis.size() << endl;
    for (auto v : vis) {
        cerr << "(";
        rep(i, N) cerr << v.first[i] << ", ";
        cerr << ") " << v.second << endl;
    }
#endif
}