Permutation

3.9

90 votes
Algorithms, Breadth First Search, Easy, Graphs
Problem

Given a permutation of 1 to n, you need to perform some operations to make it into increasing order. Each operation is to reverse an interval a1,a2,,ax(1xn) (a prefix). Your goal is to minimize the number of operations.

Input

The first line contains an integer n (1n8).

The second line contains n space separated integers, representing the sequence a.

Output

An integer representing the answer, that is, the minimum number of operations needed to make the permutation into increasing order.

Sample Input
3
3 1 2
Sample Output
2
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

A possible way is to reverse [1,3], and then [1,2].

Contributers:
Editor Image

?