Problem Description

Indeed Corporation has $ N $ employees lined up in a row from left to right. Each employee has a defined height, and their face is visible from the left side of the line only if they are taller than all employees to their left.

The employees are already lined up, but any two adjacent employees can swap positions an arbitrary number of times. The cost of swapping positions is equal to the height of the shorter employee.

The total cost is defined as the sum of the costs of all swaps.

Now, Mr. A wants all $ N $ employees to be visible from the left side of the line, and he will only be satisfied if this condition is met.

Your task is to determine the minimum total cost required to satisfy Mr. A, given the heights of the employees in the line. If it is impossible to satisfy Mr. A regardless of how the employees are arranged, report that accordingly.

Input Format

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

$ N $ $ H_1 $ $ H_2 $ … $ H_N $

• The first line contains an integer $N\ (1 \leq N \leq 10^5)$, representing the number of employees lined up.
• The second line contains $ N $ integers separated by spaces, where the $ i $-th integer $H_i\ (1 \leq H_i \leq 10^8)$ represents the height of the employee at the $ i $-th position from the left in the line.

Output Format

Output a single line containing the minimum total cost required to satisfy Mr. A. If it is impossible to satisfy Mr. A, output -1. End the output with a newline.

Sample Input and Output

Sample Input #1

4
4 1 3 2

Sample Output #1

8

Sample Input #2

5
1 1 2 2 3

Sample Output #2

-1

Notes/Hints

Partial Points

This problem has partial scoring:

• If you solve the dataset where $1 \leq N \leq 1000$ correctly, you will be awarded 30 points.
• If you solve all test cases correctly, you will be awarded an additional 70 points.

Sample Explanation 1

By arranging the heights in the order $ 1, 2, 3, 4 $ from left to right, all faces will be visible from the left side, satisfying Mr. A. The minimum total cost to achieve this arrangement is 8, which can be achieved by the following swaps:
- First, swap the person with height 4 and the person with height 1. The cost is 1, and the sequence becomes $ 1, 4, 3, 2 $.
- Next, swap the person with height 4 and the person with height 3. The cost is 3, and the sequence becomes $ 1, 3, 4, 2 $.
- Then, swap the person with height 4 and the person with height 2. The cost is 2, and the sequence becomes $ 1, 3, 2, 4 $.
- Finally, swap the person with height 3 and the person with height 2. The cost is 2, and the sequence becomes $ 1, 2, 3, 4 $.

Sample Explanation 2

No matter how the employees are arranged, it is impossible to see the faces of people with the same height simultaneously. Therefore, the output must be -1.

见题面 Input 部分

见题面 Output 部分