Problem Description

You are given a sequence $ A $ of length $ N $.

For this sequence, you can perform the following two types of operations:

• Swap two adjacent elements.
• Choose any element and increase its value by $ 1 $.

Determine the minimum number of operations required to make the sequence $ A $ a non-decreasing sequence by repeating these operations.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ A_2 $ $ : $ $ A_N $

Output Format

Output the minimum number of operations required to make the sequence $ A $ non-decreasing.

Sample Input and Output

Sample Input #1

5
4
1
8
8
7

Sample Output #1

2

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

Notes/Hints

Constraints

• $1\ \leq\ N\ \leq\ 200000$
• $1\ \leq\ A_i\ \leq\ 10^9$
• $ A_i $ is an integer.

Sample Explanation 1

You can make $ A $ non-decreasing with $ 2 $ operations as follows:
- Initially, $A\ =\ \{4,\ 1,\ 8,\ 8,\ 7\}$.
- Swap the first two elements, resulting in $A\ =\ \{1,\ 4,\ 8,\ 8,\ 7\}$.
- Increase the last element by $ 1 $, resulting in $A\ =\ \{1,\ 4,\ 8,\ 8,\ 8\}$.

见题面 Input 部分

见题面 Output 部分