Given a wooden stick of length n units. The stick is labelled from 0 to n. You are given an integer array cuts where cuts[i] denotes a position you should perform a cut at.

The cost of making a cut is the length of the stick being cut. You want to minimize the total cost.

Example 1:

Input: n = 7, cuts = [1,3,4,5]
Output: 16

Example 2:

Input: n = 9, cuts = [5,6,1,4,2]
Output: 22

Constraints:

• 2 <= n <= 10^6
• 1 <= cuts.length <= min(n - 1, 100)