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.

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.