You are given a stick of length n with positions labeled from $0$ to n. You must perform a cut at every position listed in cuts.

When you cut a stick segment, the cost of that cut equals the current length of the segment being cut. After making a cut, the segment is split into two smaller segments, and future cuts are applied to the appropriate resulting segment.

Return the minimum total cost to perform all cuts in cuts, where you may choose the order of cuts.

Constraints:

• $2 \leq$ n $\leq 10^6$

• $1 \leq$ cuts.length $\leq \min(n $-$ $1$, $100)$

• $1 \leq$ cuts[i] $\leq$ n $-$ $1$

• All integers in cuts are distinct.

Input: n = 8-int, cuts = [2, 6]-List[int]
Output: 14-int
Explanation: Cutting at 2 first costs 8 (cutting the whole stick), then cutting the remaining segment [2, 8] at 6 costs 6, for a total of 8 + 6 = 14. (Cutting at 6 first also gives a total of 8 + 6 = 14.)

Input: n = 10-int, cuts = [4]-List[int]
Output: 10-int
Explanation: Only one cut is required, and it cuts the full stick of length 10, so the cost is 10.

Input: n = 20-int, cuts = [1, 3, 7, 8, 12, 16]-List[int]
Output: 55-int
Explanation: The optimal strategy chooses an order that minimizes repeatedly cutting long segments. Dynamic programming over intervals (after sorting the cuts and adding boundaries 0 and 20) finds the minimum total cost across all possible “first cut” choices per segment, yielding 55.

Input: n = 1000000-int, cuts = [1, 999999, 500000, 250000, 750000, 125000, 875000]-List[int]
Output: 2750000-int
Explanation: Even with a very large stick, the number of cuts is small (≤ 100). The optimal plan tends to cut near the middle first to avoid paying the full length too many times, and interval DP computes the minimum total cost as 2,750,000.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.