Minimizing Soil Removal to Achieve a Given Number of Peaks

Farmer John is converting his goat farm into a dairy farm – but his land, originally designed for goats, is too rocky. In order to raise cows he must remove as little soil as possible so that the resulting landscape has exactly (k) mountain peaks. The farm is represented as a one‐dimensional array of (n) positive integers (each in the range ([1,10^6])), where each integer denotes the elevation at that position. A mountain peak is defined as one or more consecutive positions of equal elevation, such that if you look immediately to the left and to the right of that contiguous block (treating missing neighbors as having elevation (0)), both neighbors have strictly lower elevation than the peak.

For example, consider the farm

1 2 3 3 3 2 1 3 2 2 1 2

which may be pictured as:

    * * *     *
  * * * * *   * * *   *
* * * * * * * * * * * *
1 2 3 3 3 2 1 3 2 2 1 2

This farm has three peaks: the contiguous block of three 3’s in the middle, the single 3 later in the array, and the right‐end 2 (since its missing right neighbor is treated as 0).

The only operation allowed is to lower the elevation of any position; lowering one unit of elevation removes one unit of soil. You cannot add soil. Your task is to compute the minimum volume of soil that must be removed so that the final landscape has exactly (k) peaks. The final elevation at every position must be an integer not greater than its original elevation, and the peaks are recalculated according to the rule above, using the final elevations.

inputFormat

The first line of input contains two integers (n) and (k) (with (1 \le n \le 10^6); however, for this problem the test cases will be small) separated by a space. The second line contains (n) positive integers representing the elevations of the farm, separated by spaces.

outputFormat

Output a single integer: the minimum total volume of soil that must be removed so that the resulting landscape has exactly (k) peaks.

sample

12 1
1 2 3 3 3 2 1 3 2 2 1 2

5