Plate Sorting Challenge

In this problem, you are given a stack of plates (or weights) that are arranged in a random order. The plates are not in ascending order by weight, which makes gradual training difficult. To fix this, you are allowed to perform a specific operation: you can take the top k plates (2 ≤ k ≤ n) of the stack and flip them, which reverses their order.

Your task is to determine the minimum number of flips required to arrange the plates in ascending order (i.e. from smallest at the top to largest at the bottom).

For example, consider the following case:

• Initial stack: 3 1 2
• Flip the top 3 plates: 2 1 3
• Flip the top 2 plates: 1 2 3

The plates are now sorted. Thus, the answer is 2 flips.

It is guaranteed that the number of plates n is small (for instance, n ≤ 10), so that an exhaustive search (such as BFS) is feasible.

inputFormat

The first line contains a single integer n — the number of plates.

The second line contains n space-separated integers representing the weights of the plates from top to bottom.

outputFormat

Output a single integer — the minimum number of flips required to sort the plates in ascending order.

sample

3
3 1 2

2