题目描述

有一个长度为 $N$ 的数列 $A$。

对于该数列，你可以进行以下两种操作：

• 交换相邻的两个元素。
• 任意选择一个元素，将它的值增加 $1$。

你可以多次执行上述操作，求将数列 $A$ 变为广义单调不减序列所需的最少操作次数。

输入格式

输入以以下格式从标准输入读入。

$N$ $A_1$ $A_2$ $…$ $A_N$

输出格式

输出将数列 $A$ 变为广义单调不减序列所需的最小操作次数。

输入输出样例 #1

输入 #1

5
4
1
8
8
7

输出 #1

2

输入输出样例 #2

输入 #2

20
8
2
9
7
4
6
7
9
7
4
7
4
4
3
6
2
3
4
4
9

输出 #2

62

说明/提示

限制条件

• $1 \leq N \leq 200000$
• $1 \leq A_i \leq 10^9$
• $A_i$ 为整数。

样例解释 1

可以通过如下两步操作将 $A$ 变为单调不减序列：

• 初始时 $A = \{4, 1, 8, 8, 7\}$。
• 首先交换前两个元素，得到 $A = \{1, 4, 8, 8, 7\}$。
• 然后将最后一个元素增加 $1$，得到 $A = \{1, 4, 8, 8, 8\}$。

由 ChatGPT 5 翻译