実行時間制限: 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