A straight timber plank spans from position 0 to position L. It must be cut at a fixed set of m distinct interior mark positions (each strictly between 0 and L). Every cut is a full crosscut through whichever single piece currently contains that mark, and it costs the current length of that piece (the distance between the two ends of that piece).
You may perform the required cuts in any order; a cut only ever affects the piece it lands in. Choose the order of cuts that minimizes the total cost, and report that minimum.
Input format
Line 1: two integers L and m, the plank length and the number of cut marks.
Line 2: m space-separated distinct integers, the interior mark positions (each in the range 1..L-1). This line is empty when m is 0.
Output format
A single integer: the minimum total cutting cost (0 when there are no marks).
Constraints
- 1 <= L <= 1000000
- 0 <= m <= 100
- All mark positions are distinct and strictly between 0 and L.