AT_awtf2024_d Almost Bubble Sort

给定一个长度为 $N$ 的排列 $P=(P_1, P_2, \cdots, P_N)$。我们希望通过若干次相邻元素交换，使排列 $P$ 满足下面的条件： - 在所有 $i$ 中，满足 $P_i > P_{i+1}$ 的 $i$ 的数量最多为 1 个。 请找出使 $P$ 满足条件所需的最小交换次数。

输入通过标准输入给出，格式如下： > $N$ $P_1$ $P_2$ $\cdots$ $P_N$

输出结果所需的交换次数。

- $2 \leq N \leq 800000$ - $(P_1, P_2, \cdots, P_N)$ 是 $(1, 2, \cdots, N)$ 的一个排列 - 输入的所有值均为整数 ### 样例说明 通过交换 $P_1$ 和 $P_2$，可以将 $P$ 变为 $(2, 3, 1)$，此时排列满足条件。 **本翻译由 AI 自动生成**