AT_past202306_k 入れ替えてソート

有一个长度为 $N$ 的序列 $P = (P_1, P_2,\ldots, P_N)$，该序列是 $1,2,\ldots,N$ 的一个排列。 你可以对该序列进行如下任意次数（可以为零）的操作： - 选择一个整数 $i$，满足 $1 \leq i \leq N-1$，交换 $P$ 的第 $i$ 个元素和第 $i+1$ 个元素。此次操作的代价为被交换的两个数之和。 请计算将 $P$ 排序为升序所需的最小总代价。

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

输出最小总代价。

## 样例解释 1 例如，通过以下三次操作，可以将 $P$ 按升序排列： - 选择 $i=1$，交换 $3$ 和 $2$，代价为 $5$，序列变为 $(2,3,1,4)$。 - 选择 $i=2$，交换 $3$ 和 $1$，代价为 $4$，序列变为 $(2,1,3,4)$。 - 选择 $i=1$，交换 $2$ 和 $1$，代价为 $3$，序列变为 $(1,2,3,4)$。 由于不可能用小于 $12$ 的总代价将序列升序排列，所以答案为 $12$。 ## 样例解释 3 有时可能无需进行任何操作。 # 数据范围 - $1 \leq N \leq 2\times 10^5$ - $N$ 是整数。 - $P$ 是 $1,2,\ldots,N$ 的一个排列。 由 ChatGPT 5 翻译