Background

Description

After deciphering the runic language, Little FF opened a path leading underground. At the very bottom, he found a massive stone gate ahead, carved with a scene of ancient people performing some kind of activity. Above the gate, in ancient script, were the words "Hall of the Gods." Little FF guessed the royal legacy must be inside. But the problem now is how to open the gate.

After careful study, he realized the carving roughly says: the ancients believed that only the wise could most easily approach the gods. The smartest one was often chosen through a ritual. The ritual was: the retiring sage wrote an unordered sequence of numbers for his candidates and let them perform an operation—swapping two adjacent elements in the sequence. Whoever could transform the original sequence into a nondecreasing sequence with the fewest swaps would become the next sage.

Little FF also found $n$ numbers on the gate. He thus believed the secret to opening it is to find the minimum number of swaps needed to make this sequence nondecreasing. But Little FF doesn't know how... so he came to you again, promising a 30–70 split after the job is done.

Output Format

Output a single integer $\mathit{ans}$, the minimum number of operations.

4
2 8 0 3

3

Hint

Constraints

• For $30\%$ of the testdata, $1 \le n \le 10^4$.
• For $100\%$ of the testdata, $1 \le n \le 5 \times 10^5$, $A_i \in [-2^{31}, 2^{31})$.

Sample Explanation

The initial sequence is $[2,8,0,3]$, and the target sequence is $[0, 2, 3, 8]$. One way to reach the target in three operations:

1. Swap $(8,0)$, the sequence becomes $[2,0,8,3]$.
2. Swap $(2,0)$, the sequence becomes $[0,2,8,3]$.
3. Swap $(8,3)$, the sequence becomes $[0,2,3,8]$.

Translated by ChatGPT 5