33115번 - Feng Shui 다국어

You own $N$ flower pots (numbered from $1$ to $N$) displayed in order from west to east. Each flower pot has a different height; flower pot $i$ is the $A_i$^th shortest flower pot by height. In other words, the array $[A_1, A_2, \dots , A_N ]$ is a permutation of $[1, 2, \dots , N]$.

After learning about Feng Shui (a practice of arranging pieces in living spaces to create balance), your house is healthier if you arrange the flower pots as follows. There should exist an integer $k$ such that $1 ≤ k ≤ N$, $A_i > A_{i+1}$ for all $1 ≤ i < k$, and $A_i < A_{i+1}$ for all $k ≤ i < N$. You are allowed to swap adjacent flower pots zero or more times.

As the flower pots are fragile, you want to minimize the number of swaps. Determine the minimum number of swaps such that the flower pots follow the Feng Shui rule.

The first line consists of an integer $N$ ($1 ≤ N ≤ 300\, 000$).

The second line consists of $N$ integers $A_i$ ($1 ≤ A_i ≤ N$). The array $A$ is a permutation of $[1, 2, \dots , N]$.

Output a single integer representing the minimum number of swaps such that the flower pots follow the Feng Shui rule.