Mock CCO '18 Contest 3 Problem 2 - Roger Delegates Work to Jessica

View as PDF

Submit solution


Points: 30 (partial)
Time limit: 0.25s
Memory limit: 64M

Problem types

It's the day of the Don Mills Programming Gala! Roger's professional advertising skills have gotten N students to come to the contest!

The DMPG has a reputation for being a premier programming contest in Canada, but that doesn't stop some students from failing to appreciate all of Roger's efforts. Roger assigns all of these students a monkeyness level. He now needs to check in all of these monkeys into DMPG. Magically, Roger has discerned that no two of these monkeys are identical in terms of how much of a monkey they are.

Roger wishes to check in the students in increasing monkeyness level. However, the students have lined up in arbitrary order, so he dispatches his loyal assistant Jessica to handle this.

Jessica, unlike Roger, is not a monkey. She can convince any two monkeys with monkeyness levels X and Y to switch positions, but it will increase her frustration by X+Y units. Compute the minimum frustration Jessica will have after sorting all of the monkeys.

Constraints

1 \le N \le 10^4

1 \le x_i \le 10^5

All x_i are distinct.

Input Specification

The first line will contain a single integer N.

Each of the next N lines will contain an integer x_i, the monkeyness of the ith person in line.

Output Specification

Output the minimum frustration Jessica can have after sorting all the monkeys.

Sample Input

3
2
3
1

Sample Output

7

Comments

There are no comments at the moment.