연습반의 기준 구간

문제

한 학원에서는 다음 달에 사용할 연습 자료를 점검하기 위해 임시 연습반을 만든다. 참여를 신청한 학생은 N명이며, 각 학생에게는 사전 연습에서 정해진 정수 단계가 하나씩 있다. 단계가 같은 학생도 서로 다른 학생으로 센다. 담당자는 신청자 가운데 정확히 K명을 골라 연습반을 구성해야 한다. 연습반에서 사용할 자료는 하나의 기준 구간으로 준비한다. 선택한 학생들의 단계 중 가장 작은 값을 L, 가장 큰 값을 R이라고 할 때, 담당자는 L단계부터 R단계까지의 자료를 준비한다. 선택한 학생이 없는 단계도 구간 안에 있으면 함께 준비한다. 학원에서는 이 구간의 양 끝 단계 차이인 R-L을 준비 부담으로 정했다. 따라서 모든 학생의 단계가 같거나 학생을 한 명만 선택했다면 준비 부담은 0이다. 담당자의 첫 번째 목표는 준비 부담이 가장 작은 연습반을 만드는 것이다. 준비 부담이 같은 연습반이 여러 개라면, 그중 L이 가장 작은 연습반의 기준 구간을 사용한다. 이 두 조건까지 같다면 어떤 학생들을 선택했는지는 구분하지 않는다. 준비 부담과 L이 같으면 R도 같으므로 출력할 기준 구간은 하나로 정해진다. 신청 순서는 학생을 선택하는 데 영향을 주지 않으며, 입력에서 이웃한 학생들을 함께 선택할 필요도 없다. 또한 기준 구간에 단계가 들어가는 모든 신청자를 반드시 선택하는 것은 아니다. 같은 단계를 가진 신청자가 많더라도 연습반의 인원은 정확히 K명이어야 한다. 모든 신청자의 단계가 주어질 때, 위 규칙으로 정해지는 준비 부담과 기준 구간의 양 끝 L, R을 구하는 프로그램을 작성한다. K는 N 이하이므로 연습반을 구성할 수 없는 경우는 없다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 1 ≤ K ≤ N ≤ 30,000이다.
둘째 줄에 각 신청자의 단계를 나타내는 정수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. 모든 i에 대해 0 ≤ A_i ≤ 1,000,000이다. 같은 단계가 여러 번 주어질 수 있다.

출력

최소 준비 부담 R-L, 동점 처리 규칙에 따라 정해진 L, R을 차례대로 공백으로 구분하여 한 줄에 출력한다.

7 3
18 4 11 6 20 5 19

2 4 6

6 4
12 3 12 8 12 8

4 8 12

4 1
9 0 9 2

0 0 0

출처: Devin.KR 자체 제작