Description

There are $N$ bottles, numbered $1 \sim N$, placed on a shelf.

For example, there are $5$ bottles:

Each time, you are allowed to pick up $2$ bottles and swap their positions.

After several swaps, make the bottle numbers become:

For such a simple case, it is obvious that at least $2$ swaps are needed to restore the order.

What if there are more bottles? You can solve it by programming.

Input Format

The first line: a positive integer $N$ ($N<10000$), representing the number of bottles.

The second line: $N$ positive integers separated by spaces, representing the current arrangement of the bottles.

Output Format

Output one positive integer in a single line, representing the minimum number of swaps needed to finish the sorting.

5
3 1 2 5 4

3

5
5 4 3 2 1

2

Hint

Time limit: 1 second, 256M. Lanqiao Cup 2016, the 7th provincial contest.

Lanqiao Cup 2016 provincial contest, Group B, Problem I.

Translated by ChatGPT 5