smokeflower

Smoke Flower

"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.

n fireworks are arranged in a row, from left to right, with heights of h_1,h_2,\cdots,h_n, no two fireworks share the same height.

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.

Limits

For all test caes: 1\le n\le 300,000，1\le h_i\le n，h_i are distinct.

Subtask # Score n
1 6 \le 4
2 11 \le 8
3 16 \le 100
4 8 \le 300
5 13 \le 700
6 7 \le 2,000
7 6 \le 6,000
8 14 \le 60,000
9 19 \le 300,000

Input format

The first line contains a positive integer n

The second line contains n positive integers h_1,h_2,\cdots,h_n, and separated with a space.

Output format

Output an integer representing the minimum number of swaps.

Sample Input

5
3 5 4 1 2

Sample Output

5

Explanation

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.



Submitting .cpp to 'smokeflower'


You're not logged in! Click here to login

Time Limit: 1 Seconds
Memory Limit: 1024MB
Your best score: 0
Source: Classic Problem
Editorial: 1 2

Subtask Score
1 6
2 11
3 16
4 8
5 13
6 7
7 6
8 14
9 19
10 0