한 줄의 수조 안내판

문제

수족관은 여러 수조의 수온을 한눈에 비교하는 특별 안내판을 만들려고 한다. 안내판에는 선택한 수조들의 사진과 현재 수온이 함께 표시된다. 관리자는 안내판을 보는 관람객이 수온의 차이를 쉽게 이해하도록, 표시되는 수온의 범위를 가능한 한 좁게 만들기로 했다. 수조마다 수온 센서가 하나씩 있으며, 이번 작업에서는 이미 측정된 값만 사용한다. 수족관에는 번호가 1부터 N까지 붙은 수조가 있다. i번 수조에서 측정한 수온은 정수 A_i다. 관리자는 이 중 정확히 K개의 서로 다른 수조를 골라 안내판에 넣어야 한다. 수조 번호는 관리에 쓰이는 이름일 뿐이므로, 번호가 연속한 수조만 고를 필요는 없다. 같은 수온이 측정된 수조도 서로 다른 수조이며, 각각 하나씩 선택할 수 있다. 선택한 수조를 안내판에 배치하는 순서는 결과에 영향을 주지 않는다. 어떤 선택의 수온 폭은 선택한 수조들의 수온 중 최댓값에서 최솟값을 뺀 값으로 정의한다. 예를 들어 선택한 수조의 수온이 12, 15, 12라면 수온 폭은 3이다. 수조를 하나만 선택하면 최댓값과 최솟값이 같으므로 수온 폭은 0이다. 선택하지 않은 수조의 수온은 수온 폭 계산에 포함하지 않는다. 관리자는 선택한 뒤 수온을 조절하거나 센서 값을 바꿀 수 없다. 입력으로 주어진 측정값을 그대로 사용하여 정확히 K개를 골랐을 때 얻을 수 있는 수온 폭의 최솟값을 구한다. 최솟값을 만드는 선택이 여러 개여도 그 값만 출력하며, 수조 번호나 선택 순서는 출력하지 않는다. K는 N 이하이므로 조건을 만족하는 선택은 항상 존재한다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 둘째 줄에 N개의 정수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다.
1 ≤ K ≤ N ≤ 50,000이다. 모든 i에 대해 0 ≤ A_i ≤ 999이다.

출력

정확히 K개의 수조를 선택했을 때 가능한 수온 폭의 최솟값을 정수 하나로 출력한다.

6 3
18 11 15 12 25 14

3

5 4
7 7 7 7 9

0

1 1
0

0

출처: Devin.KR 자체 제작