← 返回题目列表

AtCoder · cf17_exhibition_b

B. 增量和交换

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

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