Compute minimal cost to merge numbers

Given an array of positive integers, you may repeatedly perform the following operation until one number remains: choose any two numbers x and y, pay a cost of x + y, and insert x + y back into the array. Compute the minimal possible total cost. Describe the algorithm, prove why it is optimal, analyze time and space complexity, and implement it in C++. Discuss edge cases such as n = 1, duplicate values, and very large integers.