B - Increment and Swap 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 1500 点

問題文

長さ 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

Score : 1500 points

Problem Statement

We have a sequence A of length N.

On this sequence, we can perform the following two kinds of operations:

  • Swap two adjacent elements.

  • Select one element, and increment it by 1.

We will repeatedly perform these operations so that A will be a non-decreasing sequence. Find the minimum required number of operations.

Constraints

  • 1 ≤ N ≤ 200000
  • 1 ≤ A_i ≤ 10^9
  • A_i is an integer.

Input

Input is given from Standard Input in the following format:

N
A_1
A_2
:
A_N

Output

Print the minimum number of operations required to turn A into a non-decreasing sequence.

Sample Input 1

5
4
1
8
8
7

Sample Output 1

2

We can turn A into a non-decreasing sequence in two operations:

  • Initially, A = \{4, 1, 8, 8, 7\}.
  • Swap the first two elements. Now, A = \{1, 4, 8, 8, 7\}.
  • Increment the last element by 1. Now, A = \{1, 4, 8, 8, 8\}.

Sample Input 2

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

Sample Output 2

62