题目描述
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.
Examples
Input
5
4
1
8
8
7
Output
2
Input
20
8
2
9
7
4
6
7
9
7
4
7
4
4
3
6
2
3
4
4
9
Output
62
输入格式
见题面
输出格式
见题面
样例输入
20
8
2
9
7
4
6
7
9
7
4
7
4
4
3
6
2
3
4
4
9
样例输出
62