Minimum Cost to Cut a Stick

A stick spans positions 0 through n. Make one cut at every distinct position listed in cuts, in any order. Each cut costs the length of the current piece containing that position, then divides that piece into two. Return the minimum total cost needed to make all the requested cuts.

Example 1:

Input: n = 6
cuts = [2,4]

Output: 10

Explanation: Cut at position 2 first, paying 6. The remaining cut at position 4 lies in the piece from 2 to 6, so it costs 4. The total is 10. Reversing these two cuts has the same total.

Example 2:

Input: n = 4
cuts = [1,3]

Output: 7

Explanation: Cut at position 1 for a cost of 4, then cut the piece from 1 to 4 at position 3 for a cost of 3. The total is 7; starting at position 3 also costs 7.

Example 3:

Input: n = 10
cuts = [5]

Output: 10

Explanation: Only one cut is requested. It is made in the original length-10 stick, so the total cost is 10.

Constraints:

• 2 <= n <= 1000000
• 1 <= cuts.length <= min(n - 1, 100)
• 1 <= cuts[i] < n
• All positions in cuts are distinct.