"Hanabi, hanabi ……"

Karen was dismayed when she heard that there were no fireworks at the festival.

"We have some...it's not as big as big fireworks though."

Fortunately, Shinobu was prepared, Alice, Ayaya, Karen, Shinobu, Yoko can continue to play happily!

"Oh...! These fireworks that shoot upwards!" Karen exclaimed excitedly.

"Ah wait..." Yoko exclaimed. Karen holds a firework with a fuse lit, "Huh??"

Yoko was very excited to see beautifully arranged fireworks and of course did not want to miss this opportunity... but time seems to be running out.

At any point in time Yoko can choose two adjacent fireworks and swap them. Such swaps can take place any number of times.

At any point in time Yoko can also choose two non-adjacent fireworks and swap them, but this can be done at most once.

Your task is to help Yoko sort the height of these fireworks in increasing order from left to right with the fewest number of swaps.

For all test caes:

Subtask # | Score | |
---|---|---|

1 | ||

2 | ||

3 | ||

4 | ||

5 | ||

6 | ||

7 | ||

8 | ||

9 |

The first line contains a positive integer

The second line contains

Output an integer representing the minimum number of swaps.

5

3 5 4 1 2

5

1. Swap the fireworks in position 4 and 5, the height of the fireworks after the swap is 3, 5, 4, 2, 1

2. Swap the fireworks in position 3 and 4, the height of the fireworks after the swap is 3, 5, 2, 4, 1

3. Swap the fireworks in position 1 and 2, the height of the fireworks after the swap is 5, 3, 2, 4, 1

4. Swap the fireworks in position 2 and 3, the height of the fireworks after the swap is 5, 2, 3, 4, 1

5. Swap the fireworks in position 1 and 5, the height of the fireworks after the swap is 1, 2, 3, 4, 5

It can be shown that this is the solution with the least number of swaps.