27932번 - 어깨동무 서브태스크

문제

고연전 때 응원을 해 본 양교의 학생들이라면 양 옆 사람들과 어깨동무를 해 본 경험이 있을 것이다! 어깨동무를 할 때 제일 불편할 때가 옆 사람과 키 차이가 많이 날 때이다. 옆 사람들과 키 차이가 나게 되면 응원 동작을 할 때 어깨동무를 하기가 힘들어지고 쉽게 지치게 된다.

그런데 윤헌이는 응원하던 도중, 모든 사람들은 이웃한 사람 중 하나 이상과 키 차이가 $H$보다 커지면 지친다는 사실을 깨달았다. 그리고 현재 경기 점수 차에 따라서 $H$의 값이 달라진다는 것도 발견했다! 구체적으로, 고려대가 $H$점차로 연세대를 이기고 있을 때 고려대 학생들은 자신과 이웃한 사람들과 키 차이가 $H$가 될 때까지는 지치지 않는다. 고려대와 연세대가 비기고 있다면 $H=0$이 된다. 고려대가 지고 있는 경우는 고려하지 않는다.

윤헌이는 일렬로 선 $n$명의 고려대생들 중 지친 사람이 $k$명 이하가 되기 위해서는 고려대가 경기를 최소 몇 점 차로 이기고 있어야 하는지가 궁금해졌다. 윤헌이를 위해 이를 구해 주자!

입력

첫 줄에 고려대를 응원하는 학생의 수 $n$과 지친 사람 수의 최댓값 $k$가 공백으로 구분되어 주어진다.

두 번째 줄에 $n$명의 학생의 키가 순서대로 공백으로 구분되어 주어진다.

출력

지친 사람이 $k$명 이하가 되기 위한 최소 점수 차이를 출력한다. 점수 차가 $H$라고 할 때, 사람들은 옆에 있는 사람들과 키 차이가 $H$ 이하이면 지치지 않는다.

제한

• 1ドル \le n \le 10^6$
• 0ドル \le k \le n$
• $i$번째 학생의 키를 $h_i$라고 할 때, 1ドル \le h_i \le 10^9$

서브태스크

노트

키의 단위는 마이크로미터 ($\mu m$)이다.