问题描述

我们有一个长度为 $N$ 的序列 $A$。

可以在该序列上执行以下两种操作：

• 交换相邻的两个元素。

• 选择一个元素，并将其加 $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