Minimum Merge Cost for Batch Processing

You are given n batches, each with an associated production cost. Your task is to merge all these batches into one with the minimum possible total cost.

In each merge operation, you select the two batches with the smallest costs. Suppose the selected batches have costs a and b; merging them produces a new batch with cost a+b and incurs a merge cost of a+b. The new batch then becomes available for subsequent merges.

This process repeats until only one batch remains. Formally, if you merge batches with costs a and b, the operation cost is given by:

[ \text{merge_cost} = a + b, ]

Your goal is to minimize the sum of all merge costs. This problem is equivalent to constructing an optimal binary tree (or Huffman tree) where the cost of merging is minimized.

inputFormat

The input is given from stdin and contains two lines:

1. The first line contains a single integer n (1 ≤ n ≤ 10⁵), representing the number of batches.
2. The second line contains n space-separated positive integers, each representing the production cost of a batch.

outputFormat

Output to stdout a single integer, the minimum total cost required to merge all batches into one.

4
4 6 8 12

58