농지 정리

N미터 길이의 일직선 농지가 있다. 각 위치에는 높이가 하나씩 주어진다. 높이가 같은 하나 이상의 연속한 구간을 보자. 그 구간의 높이가 왼쪽 이웃과 오른쪽 이웃의 높이보다 모두 크면 봉우리라고 한다. 농지의 바깥쪽은 높이 0으로 본다.

다음 높이가 주어진 농지는 아래와 같은 모양이며, 봉우리는 3개이다.

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

봉우리가 너무 많으면 농작물을 경작하기 어렵다. 그래서 몇몇 위치의 땅을 깎아 봉우리의 개수를 K개 이하로 줄이려고 한다. 위 그림에서 아래와 같이 5개의 *를 잘라내면 봉우리는 1개가 된다.

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

땅을 깎는 비용은 매우 크므로, 잘라내는 *의 개수를 최소화해야 한다. 농지의 높이 정보와 K가 주어질 때, 봉우리의 개수를 K개 이하로 만들기 위해 제거해야 하는 *의 최소 개수를 구하라.

첫째 줄에 농지의 길이 N(1 <= N <= 1,000)과 정수 K(1 <= K <= 25)가 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 위치의 높이 h(1 <= h <= 1,000,000)가 차례대로 주어진다.

봉우리의 개수를 K개 이하로 만들기 위해 최소로 제거해야 하는 *의 개수를 출력한다.