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 <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

#define dump(a) (cerr << (#a) << " = " << (a) << endl)
#define FOR(it,c) for(__typeof((c).begin())it=(c).begin(); it!=(c).end();++it)
#define RFOR(it,c) for(__typeof((c).rbegin())it=(c).rbegin(); it!=(c).rend();++it)
#define exist(c, v) (find((c).begin(), (c).end(), (v)) != (c).end())

template<class T> inline void chmax(T& a, const T& b) { if(b > a) a = b; }
template<class T> inline void chmin(T& a, const T& b) { if(b < a) a = b; }

template<typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os << '(' << p.first << ", " << p.second << ')';
	return os;
}

template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
	copy(v.begin(), v.end(), ostream_iterator<T>(os, " "));
	return os;
}

void bfs(const vector<int>& vec, map<vector<int>, int>& m) {
	const int len = vec.size();
	queue<pair<int, vector<int> > > que;
	que.push(make_pair(0, vec));
	m[vec] = 0;

	while(!que.empty()) {
		const int cnt = que.front().first;
		const vector<int> state = que.front().second;
		que.pop();

		if(cnt == 4)
			break;

		for(int l = 0; l < len; ++l) {
			for(int r = l + 1; r < len; ++r) {
				vector<int> tmp(state);
				reverse(tmp.begin() + l, tmp.begin() + r + 1);
				if(!m.count(tmp)) {
					m[tmp] = cnt + 1;
					que.push(make_pair(cnt + 1, tmp));
				}
			}
		}
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;

	vector<int> vec(n);
	for(int i = 0; i < n; ++i)
		cin >> vec[i];

	map<vector<int>, int> a, b;
	bfs(vec, a);
	sort(vec.begin(), vec.end());
	bfs(vec, b);

	int ans = 9;
	FOR(it, a) {
		map<vector<int>, int>::const_iterator it2 = b.find(it->first);
		if(it2 != b.end())
			chmin(ans, it->second + it2->second);
	}

	cout << ans << endl;

	return EXIT_SUCCESS;
}