Farmland Leveling

There is a straight one-dimensional farmland of length N meters. Each position has a height. Consider a contiguous segment of one or more positions with the same height. If that height is greater than the heights of the neighboring segments on both sides, the segment is called a peak. The outside of the farmland is treated as height 0.

For the height sequence below, the farmland has the following shape and contains 3 peaks.

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

If there are too many peaks, it becomes difficult to grow crops. You want to cut down some positions so that the number of peaks becomes at most K. In the figure above, removing 5 * marks as shown below reduces the number of peaks to 1.

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

Cutting the land is expensive, so the number of removed * marks must be minimized. Given the heights of the farmland and K, compute the minimum number of * marks that must be removed to make the number of peaks at most K.

The first line contains the farmland length N (1 <= N <= 1,000) and an integer K (1 <= K <= 25). Each of the next N lines contains one height h (1 <= h <= 1,000,000), in order.

Output the minimum number of * marks that must be removed so that the number of peaks is at most K.