같은 시간에 끝내는 업데이트

문제

사내 IT 지원팀은 직원들의 업무용 단말기에 새 지원 도구를 설치하려 한다. 설치 신청을 받은 단말기는 N대이며, 각 단말기에는 현재 설치된 도구의 버전을 나타내는 정수가 기록되어 있다. 버전 번호가 같은 단말기도 서로 다른 단말기이므로 각각 한 대로 센다. 신청 목록의 순서는 직원이 신청한 순서일 뿐이며, 함께 작업할 단말기를 고르는 데에는 영향을 주지 않는다. 지원팀은 이번 작업 시간에 정확히 K대를 골라 하나의 작업 묶음으로 처리한다. 단말기를 고를 때 신청 목록에서 연속한 위치에 있는 단말기를 고를 필요는 없다. 다만 한 단말기를 두 번 고를 수는 없다. 선택한 단말기들의 버전 차이가 크면 추가 점검이 필요하므로, 지원팀은 작업 묶음의 버전 폭을 작게 만들고 싶다. 작업 묶음에서 가장 작은 버전을 L, 가장 큰 버전을 R이라고 할 때, 버전 폭은 R-L이다. 지원팀은 가능한 모든 선택 중 버전 폭이 가장 작은 묶음을 사용한다. 최소 버전 폭을 만드는 묶음이 여러 개라면 L이 가장 작은 묶음을 사용한다. 버전 폭과 L이 모두 같으면 R도 같으므로 단말기의 신청 순서나 번호를 이용한 추가 동점 처리는 하지 않는다. 예를 들어 버전이 같은 단말기만으로 K대를 고를 수 있다면 버전 폭은 0이 될 수 있다. K가 1인 경우에도 버전 폭은 0이며, 동점 규칙에 따라 전체 신청 목록에서 가장 작은 버전이 선택된다. K가 N이면 모든 단말기를 하나의 묶음으로 처리한다. 지원팀이 사용할 묶음의 최소 버전 폭과 양 끝 버전 L, R을 구하는 프로그램을 작성한다. 실제로 선택한 단말기의 목록은 출력하지 않는다. 입력에서는 K가 N을 넘지 않으므로 작업 묶음을 만들 수 없는 경우는 없다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 1≤K≤N≤60,000이다.
둘째 줄에 각 단말기의 버전 번호를 나타내는 정수 N개가 공백으로 구분되어 주어진다. 각 버전 번호는 0 이상 9,999 이하이다.

출력

최소 버전 폭, 동점 규칙에 따라 결정한 L, R을 이 순서대로 공백으로 구분하여 한 줄에 출력한다.

7 3
8 2 6 2 9 4 7

2 2 4

5 3
5 1 5 5 9

0 5 5

4 1
7 0 3 0

0 0 0

출처: Devin.KR 자체 제작