시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB417571.429%

문제

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)가 주어진다.

출력

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

예제 입력 1

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

예제 출력 1

5
W3sicHJvYmxlbV9pZCI6IjE4NDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIxOGRcdWM5YzAgXHVjODE1XHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5OXHViYmY4XHVkMTMwXHVjNzU4IFx1YWUzNCAxXHVjYzI4XHVjNmQwIFx1YjE4ZFx1YzljMFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM5YzBcdWM1ZWRcdWM1ZDBcdWIyOTQgXHVhZGY4IFx1YzljMFx1YzVlZFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YjE5Mlx1Yzc3NFx1YWMwMCBcdWFjMTlcdWM3NDAgXHVkNTVjIFx1YWMxYyBcdWM3NzRcdWMwYzFcdWM3NTggXHVjNWYwXHVjMThkXHViNDFjIFx1YWQ2Y1x1YWMwNFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWFjMDAsIFx1YzU5MSBcdWM2MDZcdWM3NTggXHViMTkyXHVjNzc0XHViY2Y0XHViMmU0IFx1YjE5Mlx1Yzc0NCBcdWFjYmRcdWM2YjAgXHVhZGY4IFx1YWQ2Y1x1YWMwNFx1Yzc0NCBcdWJkMDlcdWM2YjBcdWI5YWNcdWI3N2NcdWFjZTAgXHViZDgwXHViOTc4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM1N2RcdWM1ZDAgXHViMTkyXHVjNzc0XHVhYzAwIDEsIDIsIDMsIDMsIDMsIDIsIDEsIDMsIDIsIDIsIDEsIDJcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YjE4ZFx1YzljMFx1YWMwMCBcdWM3ODhcdWIyZTRcdWJhNzQgXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWM3NzQgXHViNDE4XHVjNWI0IFx1YmQwOVx1YzZiMFx1YjlhY1x1Yzc1OCBcdWMyMThcdWIyOTQgM1x1YWMxY1x1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgICAqICogKiAgICAgKlxyXG4gICogKiAqICogKiAgICogKiAqICAgKlxyXG4qICogKiAqICogKiAqICogKiAqICogKlxyXG4xIDIgMyAzIDMgMiAxIDMgMiAyIDEgMjxcL3ByZT5cclxuXHJcbjxwPlx1YWRmOFx1YjdmMFx1YjM3MCBcdWJkMDlcdWM2YjBcdWI5YWNcdWFjMDAgXHViMTA4XHViYjM0IFx1YjljZVx1Yzc0NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHViMThkXHVjOWMwXHVjNWQwXHVjMTFjIFx1YjE4ZFx1Yzc5MVx1YmIzY1x1Yzc0NCBcdWFjYmRcdWM3OTFcdWQ1NThcdWFlMzBcdWFjMDAgXHVkNzk4XHViNGU0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWJhODcgXHVhYzFjXHVjNzU4IFx1YzljMFx1YzVlZFx1Yzc0NCBcdWFlNGVcdWM1NDRcdWMxMWMgXHViZDA5XHVjNmIwXHViOWFjXHVjNzU4IFx1YzIxOFx1Yjk3YyBLXHVhYzFjIFx1Yzc3NFx1ZDU1OFx1Yjg1YyBcdWM5MDRcdWM3NzRcdWI4MjQgXHVkNTVjXHViMmU0LiBcdWM3MDRcdWM3NTggXHVhZGY4XHViOWJjXHVjNWQwXHVjMTFjIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgNSBcdWFjMWNcdWM3NTggPGNvZGU+KjxcL2NvZGU+XHVjNzQ0IFx1Yzc5OFx1Yjc3Y1x1YjBiNFx1YmE3NCBcdWJkMDlcdWM2YjBcdWI5YWNcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IDFcdWFjMWNcdWI4NWMgXHVjOTA0XHVjNWI0XHViNGU0XHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuICAgICogKiAqICAgICAtXHJcbiAgKiAqICogKiAqICAgLSAtIC0gICAtXHJcbiogKiAqICogKiAqICogKiAqICogKiAqXHJcbjEgMiAzIDMgMyAyIDEgMSAxIDEgMSAxPFwvcHJlPlxyXG5cclxuPHA+XHViNTQ1XHVjNzQ0IFx1YWU0ZVx1YjI5NCBcdWIzNzBcdWM1ZDBcdWIyOTQgXHViOWU0XHVjNmIwIFx1YjljZVx1Yzc0MCBcdWJlNDRcdWM2YTlcdWM3NzQgXHViNGRjXHViYmMwXHViODVjIFx1YjU0NVx1Yzc0NCBcdWFlNGVcdWIyOTQgXHViZTQ0XHVjNmE5XHVjNzQ0IFx1Y2Q1Y1x1YzE4Y1x1ZDY1NFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzk4OSBcdWM3MDRcdWM2NDAgXHVhYzE5XHVjNzc0ICpcdWI4NWMgXHVhZGY4XHViOWJjXHVjNzQ0IFx1ZDQ1Y1x1ZDYwNFx1ZDU1OFx1YzYwMFx1Yzc0NCBcdWI1NGMsIFx1Yzc5OFx1Yjc3Y1x1YjBiNFx1YjI5NCAqXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkNWNcdWMxOGNcdWQ2NTQgXHVkNTVjXHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViMThkXHVjOWMwXHVjNzU4IFx1YjE5Mlx1Yzc3NCBcdWM4MTVcdWJjZjRcdWM2NDAgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzQ0IFx1YjU0YywgXHVjZDVjXHVjMThjXHViODVjIFx1YWU0ZVx1YzU0NFx1YjBiNFx1YjI5NCAqXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMThkXHVjOWMwXHVjNzU4IFx1YWUzOFx1Yzc3NCBOKDEgJmxlOyBOICZsZTsgMSwwMDApXHVhY2ZjIEsoMSAmbGU7IEsgJmxlOyAyNSkgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE4rMVx1YmM4OFx1YzlmOCBcdWM5MDRcdWFlNGNcdWM5YzAgXHViMThkXHVjOWMwXHVjNzU4IFx1YjE5Mlx1Yzc3NCBoKDEgJmxlOyBoICZsZTsgMSwwMDAsMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWNkNWNcdWMxOGNcdWI4NWMgXHVhZTRlXHVjNTQ0XHViMGI0XHViMjk0IDxjb2RlPio8XC9jb2RlPlx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjE4NDQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJMYW5kc2NhcGluZyIsImRlc2NyaXB0aW9uIjoiPHA+RmFybWVyIEpvaG4gaXMgbWFraW5nIHRoZSBkaWZmaWN1bHQgdHJhbnNpdGlvbiBmcm9tIHJhaXNpbmcgbW91bnRhaW4gZ29hdHMgdG8gcmFpc2luZyBjb3dzLiBIaXMgZmFybSwgd2hpbGUgaWRlYWwgZm9yIG1vdW50YWluIGdvYXRzLCBpcyBmYXIgdG9vIG1vdW50YWlub3VzIGZvciBjYXR0bGUgYW5kIHRodXMgbmVlZHMgdG8gYmUgZmxhdHRlbmVkIG91dCBhIGJpdC4gU2luY2UgZmxhdHRlbmluZyBpcyBhbiBleHBlbnNpdmUgb3BlcmF0aW9uLCBoZSB3YW50cyB0byByZW1vdmUgdGhlIHNtYWxsZXN0IGFtb3VudCBvZiBlYXJ0aCBwb3NzaWJsZS48XC9wPlxyXG5cclxuPHA+VGhlIGZhcm0gaXMgbG9uZyBhbmQgbmFycm93IGFuZCBpcyBkZXNjcmliZWQgaW4gYSBzb3J0IG9mIHR3by1kaW1lbnNpb25hbCBwcm9maWxlIGJ5IGEgc2luZ2xlIGFycmF5IG9mIE4gKDEgJmx0Oz0gTiAmbHQ7PSAxMDAwKSBpbnRlZ2VyIGVsZXZhdGlvbnMgKHJhbmdlIDEuLjEsMDAwLDAwMCkgbGlrZSB0aGlzOjxcL3A+XHJcblxyXG48cHJlPlxyXG4xIDIgMyAzIDMgMiAxIDMgMiAyIDEgMiw8XC9wcmU+XHJcblxyXG48cD53aGljaCByZXByZXNlbnRzIHRoZSBmYXJtJiMzOTtzIGVsZXZhdGlvbnMgaW4gcHJvZmlsZSwgZGVwaWN0ZWQgYmVsb3cgd2l0aCBhc3Rlcmlza3MgaW5kaWNhdGluZyB0aGUgaGVpZ2h0czo8XC9wPlxyXG5cclxuPHByZT5cclxuICAgICogKiAqICAgICAqXHJcbiAgKiAqICogKiAqICAgKiAqICogICAqXHJcbiogKiAqICogKiAqICogKiAqICogKiAqXHJcbjEgMiAzIDMgMyAyIDEgMyAyIDIgMSAyXHJcbjxcL3ByZT5cclxuXHJcbjxwPkEgY29udGlndW91cyByYW5nZSBvZiBvbmUgb3IgbW9yZSBlcXVhbCBlbGV2YXRpb25zIGluIHRoaXMgYXJyYXkgaXMgYSAmcXVvdDtwZWFrJnF1b3Q7IGlmIGJvdGggdGhlIGxlZnQgYW5kIHJpZ2h0IGhhbmQgc2lkZXMgb2YgdGhlIHJhbmdlIGFyZSBlaXRoZXIgdGhlIGJvdW5kYXJ5IG9mIHRoZSBhcnJheSBvciBhbiBlbGVtZW50IHRoYXQgaXMgbG93ZXIgaW4gZWxldmF0aW9uIHRoYW4gdGhlIHBlYWsuIFRoZSBleGFtcGxlIGFib3ZlIGhhcyB0aHJlZSBwZWFrcy48XC9wPlxyXG5cclxuPHA+RGV0ZXJtaW5lIHRoZSBtaW5pbXVtIHZvbHVtZSBvZiBlYXJ0aCAoZWFjaCB1bml0IGVsZXZhdGlvbiByZWR1Y3Rpb24gY291bnRzIGFzIG9uZSB1bml0IG9mIHZvbHVtZSkgdGhhdCBtdXN0IGJlIHJlbW92ZWQgc28gdGhhdCB0aGUgcmVzdWx0aW5nIGxhbmRzY2FwZSBoYXMgbm8gbW9yZSB0aGFuIEsgKDEgJmx0Oz0gSyAmbHQ7PSAyNSkgcGVha3MuIE5vdGUgd2VsbCB0aGF0IGVsZXZhdGlvbnMgY2FuIGJlIHJlZHVjZWQgYnV0IGNhbiBuZXZlciBiZSBpbmNyZWFzZWQuPFwvcD5cclxuXHJcbjxwPklmIHRoZSBleGFtcGxlIGFib3ZlIGlzIHRvIGJlIHJlZHVjZWQgdG8gMSBwZWFrLCB0aGUgb3B0aW1hbCBzb2x1dGlvbiBpcyB0byByZW1vdmUgMiArIDEgKyAxICsgMSA9IDUgdW5pdHMgb2YgZWFydGggdG8gb2J0YWluIHRoaXMgc2V0IG9mIGVsZXZhdGlvbnM6PFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgICAqICogKiAgICAgLVxyXG4gICogKiAqICogKiAgIC0gLSAtICAgLVxyXG4qICogKiAqICogKiAqICogKiAqICogKlxyXG4xIDIgMyAzIDMgMiAxIDEgMSAxIDEgMTxcL3ByZT5cclxuXHJcbjxwPndoZXJlICYjMzk7LSYjMzk7cyBpbmRpY2F0ZSByZW1vdmVkIGVhcnRoLjxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IE4gYW5kIEs8XC9saT5cclxuXHQ8bGk+TGluZXMgMi4uTisxOiBFYWNoIGxpbmUgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBlbGV2YXRpb24uIExpbmUgaSsxIGNvbnRhaW5zIHRoZSBlbGV2YXRpb24gZm9yIGluZGV4IGkuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVGhlIG1pbmltdW0gdm9sdW1lIG9mIGVhcnRoIHRoYXQgbXVzdCBiZSByZW1vdmVkIHRvIHJlZHVjZSB0aGUgbnVtYmVyIG9mIHBlYWtzIHRvIEsuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d