問題文

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

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

• 隣り合う要素をswapする。

• 好きな要素を $1$ つ選んでその値を $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

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

• $A = \\{4, 1, 8, 8, 7\\}$ である。
• 最初の $2$ つの要素を swap すると、$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