题目描述

長さ $N$ の数列 $A$ があります。

この数列に対して、次の $2$ 種類の操作が可能です。

• 隣り合う要素をswapする。
• 好きな要素を $1$ つ選んでその値を $1$ 増やす。

これらの操作を繰り返して数列 $A$ を広義単調増加列にする時、最小で何回の操作が必要か求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $A_1$ $A_2$ $:$ $A_N$

输出格式

数列 $A$ を広義単調増加列にするのに必要な操作の最小回数を出力せよ。

题目大意

给定一个长度为 $N$ 的 $A$，支持两种操作：

• 交换相邻两个元素。

• 将任一元素 $+1$。

问要把 $A$ 变成一个单调不减的数列，至少需要多少次操作。

$1 \leq N \leq 200000 , 1 \leq A_i \leq 10^9$。

5
4
1
8
8
7

2

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

62

提示

制約

• $1\ <\ =\ N\ <\ =\ 200000$
• $1\ <\ =\ A_i\ <\ =\ 10^9$
• $A_i$ は整数である。

Sample Explanation 1

以下のように、$2$ 回の操作で $A$ を単調増加にできます。 - $A\ =\ \{4,\ 1,\ 8,\ 8,\ 7\}$ である。 - 最初の $2$ つの要素を swap すると、$A\ =\ \{1,\ 4,\ 8,\ 8,\ 7\}$ となる。 - 最後の要素を $1$ 増やすと、$A\ =\ \{1,\ 4,\ 8,\ 8,\ 8\}$ となる。