Problem Description

You are given an array of positive integers. Your task is to repeatedly perform the following operation until only one number remains in the array:

1. Choose any two numbers, x and y, from the array.
2. Pay a cost equal to x + y.
3. Remove x and y from the array and insert their sum, x + y, back into the array.

The objective is to compute the minimal possible total cost incurred over all operations until a single number remains.

Requirements

• Algorithm Description: Clearly describe the chosen algorithm.
• Optimality Proof: Provide a proof demonstrating why your algorithm yields the minimal total cost.
• Complexity Analysis: Analyze the time and space complexity of your algorithm.
• Implementation: Implement the algorithm in C++.
• Edge Case Discussion: Discuss how your solution handles edge cases, specifically:
  • An array with only one element (n = 1).
  • Arrays containing duplicate values.
  • Scenarios involving very large integer values that might exceed standard integer types.