A wooden stick spans positions 0 to n. You must cut it at every position listed in cuts (distinct, strictly between 0 and n), one cut at a time, in any order. Each cut costs the length of the piece being cut at that moment; that piece then splits in two.
Write min_cost(n: int, cuts: list[int]) -> int: the cheapest total cost.
Examples:
min_cost(10, [2, 5]): cutting at 5 first costs 10, then 2 on the piece0..5costs 5, total 15. Cutting at 2 first costs 10 + 8 = 18. Answer15.min_cost(6, [3]) == 6min_cost(4, []) == 0
Constraints: 2 <= n <= 10**6, 0 <= len(cuts) <= 100. Trying every order is factorial; aim for O(m³) in the number of cuts m.
Show hint
sort the cuts and add 0 and n as the two ends. The first cut made between two of these points costs the same wherever it is, and it splits the problem into two independent ones.