← 返回题目列表

AtCoder · arc194_b

B. 最低成本排序

中文机器翻译题面 查看原题

分数: 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