分数: 1500 点
问题陈述
我们有一个序列 A 长度 N.
在此序列上,我们可以执行以下两种操作:
-
交换两个相邻元素。
-
选择一个元素,并将其增加 1.
我们将重复执行这些操作,以便 A 将是一个非递减序列。找出所需的最少操作次数。
约束
- 1 ≤ N ≤ 200000
- 1 ≤ A_i ≤ 10^9
- A_i 是一个整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 : A_N
输出
打印转动所需的最少操作次数 A 转换为非递减序列。
样本输入 1
5 4 1 8 8 7
示例输出 1
2
我们可以转 通过两次操作将 A 转换为非递减序列:
- 最初, 黑板上写着 A = \{4, 1, 8, 8, 7\}.
- 交换前两个元素。现在, A = \{1, 4, 8, 8, 7\}.
- 将最后一个元素增加 1。现在, 与 A = \{1, 4, 8, 8, 8\}.
示例输入 2
20 8 2 9 7 4 6 7 9 7 4 7 4 4 3 6 2 3 4 4 9
示例输出 2
62