题目描述

Farmer John（约翰农夫）正在经历一项艰难的转型——从养山羊改为养奶牛。但他现在的农场虽然非常适合山羊，却因为地势崎岖，对奶牛来说并不友好。他希望通过削平农场地形，使其更适合奶牛养殖。

农场是一个狭长的矩形，我们可以用一个整数数组来描述其从左到右的地势轮廓，如：

1 2 3 3 3 2 1 3 2 2 1 2,

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

问题要求

给定一个高度数组和一个目标高峰数 $K$，你需要通过降低某些位置的高度（每降低 $1$ 视作消耗 $1$ 单位土方体积），将整个地形修改成至多 $K$ 个高峰。

你不能升高任何位置的高度，只能降低。你的目标是使得总移除土方的体积最小。

输入格式

第 1 行：两个整数 $N, K$（分别为地形长度和目标高峰数）$；

第 2 至第 $N+1$ 行：每行一个整数，表示高度 $H_i \in [1, 10^6]$。

输出格式

第 1 行：输出为了将高峰数减少至 $K$ 所需的最少移除土方体积总量$。

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

5