分数: 600 点
问题陈述
给你一个排列 P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N)。高桥可以重复执行以下操作 P (可能为零次):
- 选择一个整数 i 满意 1 \leq i \leq N-1。支付费用 i,并交换 P_i 和 P_{i+1}.
找出排序所需的最小总成本 P 按升序排列。
约束
- 2 \leq N \leq 2 \times 10^5
- (P_1, P_2, \ldots, P_N) 是一个排列 (1, 2, \ldots, N).
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N P_1 P_2 \ldots P_N
输出
打印排序所需的最低总成本 P 按升序排列。
示例输入 1
3 3 2 1
示例输出 1
4
高桥可以排序 P 按升序排列如下:
- 支付费用 1 并交换 P_1 = 3 和 P_2 = 2。现在, P = (2, 3, 1).
- 支付费用 2 并交换 P_2 = 3 和 P_3 = 1。现在, P = (2, 1, 3).
- 支付费用 1 并交换 P_1 = 2 和 P_2 = 1。现在, P = (1, 2, 3).
这些操作的总成本为 4,这是可能的最小值。
示例输入 2
5 2 4 1 3 5
示例输出 2
6
示例输入 3
2 1 2
示例输出 3
0