시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 10 3 2 50.000%

문제

N미터의 긴 1차원 농지가 있다. 각각의 지역에는 그 지역의 높이가 주어져 있다. 그리고 높이가 같은 한 개 이상의 연속된 구간의 높이가, 양 옆의 높이보다 높을 경우 그 구간을 봉우리라고 부른다.

만약에 높이가 1 2 3 3 3 2 1 3 2 2 1 2로 주어진 농지가 있다면 아래 그림과 같이 되어 봉우리의 수는 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가 주어져 있을 때, 최소로 깎아내는 *의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 농지의 길이 N(1≤N≤1,000)과 K(1≤K≤25) 가 주어진다. 그리고 두 번째 줄부터 N+1번째 줄까지 농지의 높이 h(1≤h≤1,000,000)가 주어진다.

출력

첫 줄에 최소로 깎아내는 *의 개수를 출력한다.

예제 입력

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

예제 출력

5

힌트