Description

During training, some arm-strength equipment is indispensable. When Xiaolong was practicing, he found that the iron plates on the weightlifting machine were placed in a very chaotic order, not arranged from light to heavy, which is not conducive to gradual training. He plans to use a very effortless method to organize these plates: each time, he picks up the top several plates and uses the machine’s force to flip them as a block. After flipping several times, the plates will be arranged from small to large. Can you help Xiaolong determine the minimum number of flips needed to sort the plates from smallest to largest?

For example: the plates below become sorted from small to large after the flips shown in the figure.

Input Format

There are two lines.
The first line contains the number of plates $N$ ($1 \leq N \leq 16$).
The second line contains $N$ distinct positive integers, which are the radii $R$ of the plates from top to bottom ($1 \leq R \leq 100$).

Output Format

Output a single positive integer, the minimum number of flips required to make the plates ordered from small to large.

5
2 4 3 5 1

5

Hint

Translated by ChatGPT 5