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

using namespace std;

int n;

vector<char> v, r;

vector<pair<vector<char>, int> > v1, v2;

inline int solve()
{
	r = v; sort(r.begin(), r.end());

	int ln = n / 2 - 1, rn = n - ln - 1;

	if (n == 10) { ln--; rn--; }

	map<vector<char>, int> d1; d1[v] = 1;

	queue<vector<char> > que1; que1.push(v);

	while (!que1.empty())
	{
		vector<char> v3 = que1.front(); que1.pop();

		v1.push_back(make_pair(v3, d1[v3] - 1));

		if (d1[v3] < ln + 1)
		{
			for (int i = 0; i < n; i++)
			{
				for (int j = i + 1; j < n; j++)
				{
					vector<char> v4(v3.begin(), v3.end());

					reverse(v4.begin() + i, v4.begin() + j + 1);

					if (!d1[v4])
					{
						d1[v4] = d1[v3] + 1;

						que1.push(v4);
					}
				}
			}
		}
	}

	map<vector<char>, int> d2; d2[r] = 1;

	queue<vector<char> > que2; que2.push(r);

	while (!que2.empty())
	{
		vector<char> v3 = que2.front(); que2.pop();

		v2.push_back(make_pair(v3, d2[v3] - 1));

		if (d2[v3] < rn + 1)
		{
			for (int i = 0; i < n; i++)
			{
				for (int j = i + 1; j < n; j++)
				{
					vector<char> v4(v3.begin(), v3.end());

					reverse(v4.begin() + i, v4.begin() + j + 1);

					if (!d2[v4])
					{
						d2[v4] = d2[v3] + 1;

						que2.push(v4);
					}
				}
			}
		}
	}

	sort(v2.begin(), v2.end());

	vector<vector<char> > v5; vector<int> v6;

	for (int i = 0; i < v2.size(); i++)
	{
		v5.push_back(v2[i].first);
		v6.push_back(v2[i].second);
	}

	int ret = 999999999;

	for (int i = 0; i < v1.size(); i++)
	{
		int l = distance(v5.begin(), lower_bound(v5.begin(), v5.end(), v1[i].first));
		int r = distance(v5.begin(), upper_bound(v5.begin(), v5.end(), v1[i].first));

		if (l != r)
		{
			ret = min(ret, v1[i].second + v6[l]);
		}
	}

	return ret == 999999999 ? 8 : ret;
}

int main()
{
	scanf("%d", &n);

	v = vector<char>(n); int k;

	for (int i = 0; i < n; i++)
	{
		scanf("%d", &k); v[i] = k;
	}

	vector<char> tokushu1 = { 3, 1, 5, 2, 7, 4, 9, 6, 10, 8 };
	vector<char> tokushu2 = { 2, 4, 1, 6, 3, 8, 5, 10, 7, 9 };

	if (v == tokushu1 || v == tokushu2)
	{
		printf("9\n");
	}
	else
	{
		printf("%d\n", solve());
	}

	return 0;
}