문제
태인이의 옷장에는 $N$개의 옷이 일렬로 걸려 있다. 현재 왼쪽에서 $i$번째 옷의 색은 $c_i$이다.
태인이는 어떤 정수 $k$ (1ドル\le k\le N$)가 존재해 $c_1\leq c_2\leq\cdots\leq c_k\geq c_{k+1}\geq\cdots\geq c_N$를 만족하면 옷장이 아름답다고 생각한다.
하지만 옷장을 아름다운 상태로 정리하는 것은 꽤 귀찮다. 그래서 태인이는 옷장에서 최대 $M$개의 옷을 제거해 남은 옷들을 거의 아름다운 상태로 만들기로 했다.
최대 $M$개의 옷을 제거한 후, 남은 옷들의 개수를 $L,ドル 왼쪽에서 $j$번째 옷의 색을 $d_j$라 하자. 태인이는 인접한 두 옷의 색의 차가 $x$ 이하라면 두 옷을 같은 색으로 인식하기로 했다. 즉, 다음을 만족하는 정수 $k$ (1ドル\le k\le L$)가 존재한다면 옷장이 거의 아름다운 상태라고 한다.
- 1ドル\leq j<k$인 모든 정수 $j$에 대해 $d_j-d_{j+1}\leq x$.
- $k\leq j<L$인 모든 정수 $j$에 대해 $d_{j+1}-d_j\leq x$.
$M$개 이하의 옷을 제거해 옷장을 거의 아름다운 상태로 만들 수 있는 가장 작은 음이 아닌 정수 $x$의 값을 구하자.
출력
옷장을 거의 아름다운 상태로 만들 수 있는 가장 작은 $x$ ($x\ge 0$)의 값을 출력한다.
제한
- 1ドル\leq N\leq 10^5$
- 0ドル\leq M\leq N$
- 1ドル\leq c_i\leq 10^9$ (1ドル\leq i\leq N$)
서브태스크
| 번호 | 배점 | 제한 | | 1 | 4 | $M=0$
|
| 2 | 21 | 1ドル \leq N \leq 1,000円$
|
| 3 | 16 | 1ドル \leq c_i \leq 100$ (1ドル \leq i \leq N$)
|
| 4 | 59 | 추가적인 제약 조건이 없다.
|
노트
$x=2$일 때, 왼쪽에서 5번째 옷과 9번째 옷을 제거하면 옷장은 거의 아름다운 상태가 된다. 이보다 더 작은 $x$로는 옷장을 거의 아름다운 상태로 만들 수 없다.
W3sicHJvYmxlbV9pZCI6IjMxODE2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiQ2xvc2V0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQwZGNcdWM3NzhcdWM3NzRcdWM3NTggXHVjNjM3XHVjN2E1XHVjNWQwXHViMjk0ICROJFx1YWMxY1x1Yzc1OCBcdWM2MzdcdWM3NzQgXHVjNzdjXHViODJjXHViODVjIFx1YWM3OFx1YjgyNCBcdWM3ODhcdWIyZTQuIFx1ZDYwNFx1YzdhYyBcdWM2N2NcdWNhYmRcdWM1ZDBcdWMxMWMgJGkkXHViYzg4XHVjOWY4IFx1YzYzN1x1Yzc1OCBcdWMwYzlcdWM3NDAgJGNfaSRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDBkY1x1Yzc3OFx1Yzc3NFx1YjI5NCBcdWM1YjRcdWI1YTQgXHVjODE1XHVjMjE4ICRrJCAoJDFcXGxlIGtcXGxlIE4kKVx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NzQgJGNfMVxcbGVxIGNfMlxcbGVxXFxjZG90c1xcbGVxIGNfa1xcZ2VxIGNfe2srMX1cXGdlcVxcY2RvdHNcXGdlcSBjX04kXHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YmE3NCBcdWM2MzdcdWM3YTVcdWM3NzQgXHVjNTQ0XHViOTg0XHViMmY1XHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjIFx1YzYzN1x1YzdhNVx1Yzc0NCBcdWM1NDRcdWI5ODRcdWIyZTRcdWM2YjQgXHVjMGMxXHVkMGRjXHViODVjIFx1YzgxNVx1YjlhY1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDAgXHVhZjY0IFx1YWRjMFx1Y2MyZVx1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1ZDBkY1x1Yzc3OFx1Yzc3NFx1YjI5NCBcdWM2MzdcdWM3YTVcdWM1ZDBcdWMxMWMgXHVjZDVjXHViMzAwICRNJFx1YWMxY1x1Yzc1OCBcdWM2MzdcdWM3NDQgXHVjODFjXHVhYzcwXHVkNTc0IFx1YjBhOFx1Yzc0MCBcdWM2MzdcdWI0ZTRcdWM3NDQgPHN0cm9uZz5cdWFjNzBcdWM3NTggXHVjNTQ0XHViOTg0XHViMmU0XHVjNmI0IFx1YzBjMVx1ZDBkYzxcL3N0cm9uZz5cdWI4NWMgXHViOWNjXHViNGU0XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjZDVjXHViMzAwICRNJFx1YWMxY1x1Yzc1OCBcdWM2MzdcdWM3NDQgXHVjODFjXHVhYzcwXHVkNTVjIFx1ZDZjNCwgXHViMGE4XHVjNzQwIFx1YzYzN1x1YjRlNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgJEwkLCBcdWM2N2NcdWNhYmRcdWM1ZDBcdWMxMWMgJGokXHViYzg4XHVjOWY4IFx1YzYzN1x1Yzc1OCBcdWMwYzlcdWM3NDQgJGRfaiRcdWI3N2MgXHVkNTU4XHVjNzkwLiBcdWQwZGNcdWM3NzhcdWM3NzRcdWIyOTQgXHVjNzc4XHVjODExXHVkNTVjIFx1YjQ1MCBcdWM2MzdcdWM3NTggXHVjMGM5XHVjNzU4IFx1Y2MyOFx1YWMwMCAkeCQgXHVjNzc0XHVkNTU4XHViNzdjXHViYTc0IFx1YjQ1MCBcdWM2MzdcdWM3NDQgXHVhYzE5XHVjNzQwIFx1YzBjOVx1YzczY1x1Yjg1YyBcdWM3NzhcdWMyZGRcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWM5ODksIFx1YjJlNFx1Yzc0Y1x1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjODE1XHVjMjE4ICRrJCAoJDFcXGxlIGtcXGxlIEwkKVx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTRcdWJhNzQgXHVjNjM3XHVjN2E1XHVjNzc0IDxzdHJvbmc+XHVhYzcwXHVjNzU4IFx1YzU0NFx1Yjk4NFx1YjJlNFx1YzZiNCBcdWMwYzFcdWQwZGM8XC9zdHJvbmc+XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kMVxcbGVxIGombHQ7ayRcdWM3NzggXHViYWE4XHViNGUwIFx1YzgxNVx1YzIxOCAkaiRcdWM1ZDAgXHViMzAwXHVkNTc0ICRkX2otZF97aisxfVxcbGVxIHgkLjxcL2xpPlxyXG5cdDxsaT4ka1xcbGVxIGombHQ7TCRcdWM3NzggXHViYWE4XHViNGUwIFx1YzgxNVx1YzIxOCAkaiRcdWM1ZDAgXHViMzAwXHVkNTc0ICRkX3tqKzF9LWRfalxcbGVxIHgkLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPiRNJFx1YWMxYyBcdWM3NzRcdWQ1NThcdWM3NTggXHVjNjM3XHVjNzQ0IFx1YzgxY1x1YWM3MFx1ZDU3NCBcdWM2MzdcdWM3YTVcdWM3NDQgPHN0cm9uZz5cdWFjNzBcdWM3NTggXHVjNTQ0XHViOTg0XHViMmU0XHVjNmI0IFx1YzBjMVx1ZDBkYzxcL3N0cm9uZz5cdWI4NWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOCAkeCRcdWM3NTggXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggJE4kXHVhY2ZjICRNJFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwICROJFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggJGNfMSxjXzIsXFxsZG90cyAsY19OJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNjM3XHVjN2E1XHVjNzQ0IDxzdHJvbmc+XHVhYzcwXHVjNzU4IFx1YzU0NFx1Yjk4NFx1YjJlNFx1YzZiNCBcdWMwYzFcdWQwZGM8XC9zdHJvbmc+XHViODVjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgJHgkICgkeFxcZ2UgMCQpXHVjNzU4IFx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPiR4PTIkXHVjNzdjIFx1YjU0YywgXHVjNjdjXHVjYWJkXHVjNWQwXHVjMTFjIDVcdWJjODhcdWM5ZjggXHVjNjM3XHVhY2ZjIDlcdWJjODhcdWM5ZjggXHVjNjM3XHVjNzQ0IFx1YzgxY1x1YWM3MFx1ZDU1OFx1YmE3NCBcdWM2MzdcdWM3YTVcdWM3NDAgPHN0cm9uZz5cdWFjNzBcdWM3NTggXHVjNTQ0XHViOTg0XHViMmU0XHVjNmI0IFx1YzBjMVx1ZDBkYzxcL3N0cm9uZz5cdWFjMDAgXHViNDFjXHViMmU0LiBcdWM3NzRcdWJjZjRcdWIyZTQgXHViMzU0IFx1Yzc5MVx1Yzc0MCAkeCRcdWI4NWNcdWIyOTQgXHVjNjM3XHVjN2E1XHVjNzQ0IDxzdHJvbmc+XHVhYzcwXHVjNzU4IFx1YzU0NFx1Yjk4NFx1YjJlNFx1YzZiNCBcdWMwYzFcdWQwZGM8XC9zdHJvbmc+XHViODVjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPiQxXFxsZXEgTlxcbGVxIDEwXjUkPFwvbGk+XHJcblx0PGxpPiQwXFxsZXEgTVxcbGVxIE4kPFwvbGk+XHJcblx0PGxpPiQxXFxsZXEgY19pXFxsZXEgMTBeOSQgKCQxXFxsZXEgaVxcbGVxIE4kKTxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kTT0wJDxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+JDEgXFxsZXEgTiBcXGxlcSAxXFwsMDAwJDxcL3A+XHJcbiIsInN1YnRhc2szIjoiPHA+JDEgXFxsZXEgY19pIFxcbGVxIDEwMCQgKCQxIFxcbGVxIGkgXFxsZXEgTiQpPFwvcD5cclxuIiwic3VidGFzazQiOiI8cD5cdWNkOTRcdWFjMDBcdWM4MDFcdWM3NzggXHVjODFjXHVjNTdkIFx1Yzg3MFx1YWM3NFx1Yzc3NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMzE4MTYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDbG9zZXQiLCJkZXNjcmlwdGlvbiI6IjxwPlRhZWluIGhhcyBhIGNsb3NldCB3aXRoICROJCBjbG90aGVzIGhhbmdpbmcgaW4gaXQuIEN1cnJlbnRseSwgdGhlICRpJC10aCBjbG90aGVzIGZyb20gdGhlIGxlZnQgaGFzIGNvbG9yICRjX2kkLjxcL3A+XHJcblxyXG48cD5UYWVpbiBjb25zaWRlcnMgaGlzIGNsb3NldCBiZWF1dGlmdWwgaWYgdGhlcmUgZXhpc3RzIGFuIGludGVnZXIgJGskICgkMVxcbGUga1xcbGUgTiQpIHN1Y2ggdGhhdCAkY18xXFxsZXEgY18yXFxsZXFcXGNkb3RzXFxsZXEgY19rXFxnZXEgY197aysxfVxcZ2VxXFxjZG90c1xcZ2VxIGNfTiQuPFwvcD5cclxuXHJcbjxwPkhvd2V2ZXIsIG9yZ2FuaXppbmcgdGhlIGNsb3NldCBpbnRvIGEgYmVhdXRpZnVsIHN0YXRlIGlzIHF1aXRlIHRlZGlvdXMuIFNvLCBUYWVpbiBkZWNpZGVkIHRvIHJlbW92ZSBhdCBtb3N0ICRNJCBjbG90aGVzIGZyb20gdGhlIGNsb3NldCB0byBtYWtlIHRoZSByZW1haW5pbmcgY2xvdGhlcyA8c3Ryb25nPmFsbW9zdCBiZWF1dGlmdWw8XC9zdHJvbmc+LjxcL3A+XHJcblxyXG48cD5BZnRlciByZW1vdmluZyBhdCBtb3N0ICRNJCBjbG90aGVzLCBsZXQgJEwkIGJlIHRoZSBudW1iZXIgb2YgcmVtYWluaW5nIGNsb3RoZXMsIGFuZCBsZXQgJGRfaiQgYmUgdGhlIGNvbG9yIG9mIHRoZSAkaiQtdGggY2xvdGhlcyBmcm9tIHRoZSBsZWZ0LiBUYWVpbiBkZWNpZGVkIHRvIHJlY29nbml6ZSB0d28gYWRqYWNlbnQgY2xvdGhlcyBhcyB0aGUgc2FtZSBjb2xvciBpZiB0aGUgZGlmZmVyZW5jZSBpbiBjb2xvciBiZXR3ZWVuIHRoZW0gaXMgYXQgbW9zdCAkeCQuIEluIG90aGVyIHdvcmRzLCB0aGUgY2xvc2V0IGlzIGNhbGxlZCA8c3Ryb25nPmFsbW9zdCBiZWF1dGlmdWw8XC9zdHJvbmc+IGlmIHRoZXJlIGV4aXN0cyBhbiBpbnRlZ2VyICRrJCAoJDFcXGxlIGtcXGxlIEwkKSBmb3Igd2hpY2ggdGhlIGZvbGxvd2luZyBob2xkczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kZF9qLWRfe2orMX1cXGxlcSB4JCBmb3IgZWFjaCBpbnRlZ2VyICRqJCBzdWNoIHRoYXQgJDFcXGxlcSBqJmx0O2skLjxcL2xpPlxyXG5cdDxsaT4kZF97aisxfS1kX2pcXGxlcSB4JCBmb3IgZWFjaCBpbnRlZ2VyICRqJCBzdWNoIHRoYXQgJGtcXGxlcSBqJmx0O0wkLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkxldCZyc3F1bztzIGZpbmQgdGhlIHNtYWxsZXN0IHZhbHVlIG9mIG5vbi1uZWdhdGl2ZSBpbnRlZ2VyICR4JCB0aGF0IGNhbiBtYWtlIHRoZSBjbG9zZXQgPHN0cm9uZz5hbG1vc3QgYmVhdXRpZnVsPFwvc3Ryb25nPiBieSByZW1vdmluZyAkTSQgb3IgZmV3ZXIgY2xvdGhlcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyAkTiQgYW5kICRNJCBzZXBhcmF0ZWQgYnkgYSBzcGFjZS48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zICROJCBpbnRlZ2VycyAkY18xLGNfMixcXGxkb3RzICxjX04kIHNlcGFyYXRlZCBieSBhIHNwYWNlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IHRoZSBzbWFsbGVzdCB2YWx1ZSBvZiAkeCQgKCR4XFxnZSAwJCkgdGhhdCBjYW4gbWFrZSB0aGUgY2xvc2V0IDxzdHJvbmc+YWxtb3N0IGJlYXV0aWZ1bDxcL3N0cm9uZz4uPFwvcD5cclxuIiwiaGludCI6IjxwPldoZW4gJHg9MiQsIFRhZWluIGNhbiBtYWtlIHRoZSBjbG9zZXQgPHN0cm9uZz5hbG1vc3QgYmVhdXRpZnVsPFwvc3Ryb25nPiBieSByZW1vdmluZyB0aGUgNXRoIGFuZCA5dGggY2xvdGhlcyBmcm9tIHRoZSBsZWZ0LiBUaGVyZSBhcmUgbm8gc21hbGxlciB2YWx1ZXMgb2YgJHgkIHdoaWNoIG1ha2UgaXQgcG9zc2libGUgdG8gbWFrZSB0aGUgY2xvc2V0IDxzdHJvbmc+YWxtb3N0IGJlYXV0aWZ1bDxcL3N0cm9uZz4uPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPiQxXFxsZXEgTlxcbGVxIDEwXjUkPFwvbGk+XHJcblx0PGxpPiQwXFxsZXEgTVxcbGVxIE4kPFwvbGk+XHJcblx0PGxpPiQxXFxsZXEgY19pXFxsZXEgMTBeOSQgKCQxXFxsZXEgaVxcbGVxIE4kKTxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kTT0wJDxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+JDEgXFxsZXEgTiBcXGxlcSAxXFwsMDAwJDxcL3A+XHJcbiIsInN1YnRhc2szIjoiPHA+JDEgXFxsZXEgY19pIFxcbGVxIDEwMCQgKCQxIFxcbGVxIGkgXFxsZXEgTiQpPFwvcD5cclxuIiwic3VidGFzazQiOiI8cD5ObyBhZGRpdGlvbmFsIGNvbnN0cmFpbnRzLjxcL3A+XHJcbiJ9XQ==