配点 : $1500$ 点

問題文

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

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

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

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

制約

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

入力

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

$N$

$A_1$

$A_2$

$:$

$A_N$

出力

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

5
4
1
8
8
7

2

以下のように、$2$ 回の操作で $A$ を単調増加にできます。

• $A = \{4, 1, 8, 8, 7\}$ である。
• 最初の $2$ つの要素を swap すると、$A = \{1, 4, 8, 8, 7\}$ となる。
• 最後の要素を $1$ 増やすと、$A = \{1, 4, 8, 8, 8\}$ となる。

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

62