Card Bundle Sorting

Interview

Time limit2sMemory limit128 MB

Summary
Given N sorted card bundle sizes, find the minimum total comparisons to merge them all into one bundle using an optimal merge strategy (classic huffman-like heap problem).
Level

Easy3 of 10

Topics
Heap, Greedy
Solved
No attempts yet

Problem

You are given several sorted bundles of number cards. If two bundles contain A and B cards, merging them into one bundle requires A+B comparisons.

All bundles on the table must be merged into a single bundle. The total number of comparisons depends on the order in which pairs of bundles are chosen. For example, with bundles of 10, 20, and 40 cards, merging 10 and 20 first and then merging the resulting 30-card bundle with 40 requires (10 + 20) + (30 + 40) = 100 comparisons. If 10 and 40 are merged first, the total becomes (10 + 40) + (50 + 20) = 120 comparisons, which is less efficient.

Given the sizes of N card bundles, compute the minimum number of comparisons needed to merge all bundles into one.

Input

The first line contains the number of card bundles N. (1 ≤ N ≤ 100,000)

Each of the next N lines contains the size of one card bundle. Every bundle size is an integer between 1 and 1,000, inclusive.

Output

Print the minimum number of comparisons needed to merge all card bundles into one.

Examples1

  1. Example 1

    Input
    3
10
20
40
    Expected output
    100