ReverseSort

Interview

Time limit5sMemory limit512 MB

Summary

Given a permutation of 1 to N, find the minimum number of subarray reversals needed to sort it into ascending order.

Level: Medium5 of 10
Topics: BFS, Brute force, Sorting, Hash map
Solved: No attempts yet

Problem

You are given a permutation A1, A2, ..., AN of the N numbers from 1 to N. On this permutation you can perform the operation reverse(i, j), which reverses the order of the numbers in the range [i, j] (1 ≤ i ≤ j ≤ N). For example, applying reverse(2, 4) to [1, 2, 3, 4, 5] yields [1, 4, 3, 2, 5]. Compute the minimum number of operations needed to sort the permutation into ascending order.

Input

The input is given in the following format.

N
A1 A2 ... AN

Output

Print the answer on a single line.

Constraints

N is an integer.
2 ≤ N ≤ 10

Examples4

Example 1
Input
```
5
1 4 3 5 2
```
Expected output
```
2
```
Example 2
Input
```
5
3 1 5 2 4
```
Expected output
```
4
```
Example 3
Input
```
3
1 2 3
```
Expected output
```
0
```
Example 4
Input
```
10
3 1 5 2 7 4 9 6 10 8
```
Expected output
```
9
```