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<iostream>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>

using namespace std;
typedef vector<int> vi;
typedef map<vi, int> ma;

vi a,b;
int N;

ma bfs(vi vec){
    ma tem;
    queue<vi>que;
    que.push(vec);
    tem[vec]=0;
    while(!que.empty()){
        
        vi v=que.front();
        que.pop();
//        cout<<"tem[v]: "<<tem[v]<<endl;
//        for(int i=0;i<v.size();i++)
//            cout<<v[i]<<" ";
//        cout<<endl;
        if(tem[v]>=(N-1)/2)
            continue;
        for(int i=0;i<N;i++)
            for(int j=i+2;j<=N;j++){
                vi n=v;
                reverse(n.begin()+i,n.begin()+j);
                if(tem.find(n)==tem.end()){
                    tem[n]=tem[v]+1;
                    que.push(n);
                }
            }
    }
    return tem;
}

void solve(){
    ma m_a=bfs(a);
    ma m_b=bfs(b);
   
    if(m_a.find(b)!=m_a.end()){
        cout<<m_a[b]<<endl;
        return;
    }
    int ans=N-1;
    do{
        if(m_a.find(b)==m_a.end()||m_b.find(b)==m_b.end())
            continue;
        else
            ans=min(m_a[b]+m_b[b],ans);
    }while(next_permutation(b.begin(), b.end()));
    cout<<ans<<endl;
}

int main(){
    cin>>N;
    for(int i=0;i<N;i++){
        int t;
        cin>>t;
        a.push_back(t);
    }
    b=a;
    sort(b.begin(),b.end());
    solve();
    return 0;
}