Besley the squirrel has a pile of acorns, each with a size . Besley is willing to sell all the acorns to Wesley at a price equal to its size, that is the acorn costs dollars.
Each acorn happens to be hollow on the inside, allowing for any acorn to be placed inside another acorn if one is strictly smaller than the other.
If Wesley places an acorn of size inside another acorn of size where then he can buy both acorns for a cost of dollars, as Wesley is convinced that Besley won't play any shenanigans.
Wesley can repeat this process as many times as he wants before he buys an acorn, or choose not to place any acorns inside another.
It must hold for all acorns that if an acorn contains other acorns, the acorns contained must all be strictly smaller in size and must all be distinct in size, that is, there cannot be two acorns nested at the same level.
Can you help Wesley determine the minimum cost required in order to purchase all the acorns?
For this problem, you will NOT be required to pass all the samples in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.
For all subtasks:
Subtask 1 [50%]
Subtask 2 [50%]
No additional constraints.
The first line will contain , representing the number of acorns.
The second line will contain integers, , representing the sizes of each acorn.
This problem is graded with an
identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a
\n character and that there are no trailing spaces.
Output, on a single line, the minimum cost required for Wesley to buy all the acorns.
Sample Input 1
4 1 2 2 1
Sample Output 1
Sample Input 2
5 1 2 3 2 1
Sample Output 2
Sample Explanation 2
Besley can place acorn in acorn and acorn in acorn . He can then place either acorn or acorn in acorn , but not both.
The cost ends up being 5 dollars from 3 + 2.
Sample Input 3
6 2 4 6 1 2 3
Sample Output 3
Sample Explanation 3
Besley can end with two acorns of sizes 6 and 2 for a cost of 8 dollars.