P1774 The Person Closest to the Gods

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

破解了符文之语，小 FF 开启了通往地下的道路。当他走到最底层时，发现正前方有一扇巨石门，门上雕刻着一幅古代人进行某种活动的图案。而石门上方用古代文写着“神的殿堂”。小 FF 猜想里面应该就有王室的遗产了。但现在的问题是如何打开这扇门……。 仔细研究后，他发现门上的图案大概是说：古代人认为只有智者才是最容易接近神明的。而最聪明的人往往通过一种仪式选拔出来。仪式大概是指，即将隐退的智者为他的候选人写下一串无序的数字，并让他们进行一种操作，即交换序列中相邻的两个元素。而用最少的交换次数使原序列变成不下降序列的人即是下一任智者。 小 FF 发现门上同样有着 $n$ 个数字。于是他认为打开这扇门的秘诀就是找到让这个序列变成不下降序列所需要的最小次数。但小 FF 不会……只好又找到了你，并答应事成之后与你三七分……

第一行为一个整数 $n$，表示序列长度。 第二行为 $n$ 个整数，表示序列中每个元素。

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

### 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