건조대에 함께 올릴 옷

문제

한 세탁소에서는 세탁을 마친 옷마다 남아 있는 수분의 정도를 정수로 기록한다. 이 값을 수분값이라고 하며, 값이 작을수록 옷이 더 마른 상태이다. 오늘 사용할 보조 건조대에는 정확히 K벌을 올릴 수 있다. 세탁소에는 아직 건조대에 올리지 않은 옷이 N벌 있으며, 그중 정확히 K벌을 골라 이번 작업을 진행하려 한다. 모든 옷은 한 벌씩 따로 선택하며, 수분값이 같더라도 서로 다른 옷으로 센다. 보조 건조대는 함께 올린 옷들의 상태가 비슷할수록 관리하기 편하다. 세탁소는 선택한 옷 중 가장 큰 수분값에서 가장 작은 수분값을 뺀 값을 상태 차이라고 정했다. 이번 작업에서는 이 상태 차이가 가능한 한 작아지도록 옷을 골라야 한다. 수분값의 평균이나 합은 선택 기준에 포함되지 않는다. 입력에 적힌 순서도 선택에 영향을 주지 않으며, 서로 떨어져 적힌 옷들을 함께 골라도 된다. 상태 차이가 최소인 선택이 여러 개일 수 있다. 이때는 선택한 옷들의 가장 작은 수분값이 더 작은 선택을 우선한다. 최소 상태 차이와 가장 작은 수분값이 모두 같다면 가장 큰 수분값도 같으므로, 어떤 옷을 실제로 골랐는지는 구별하지 않는다. 프로그램은 옷의 번호나 선택한 모든 수분값을 출력할 필요가 없으며, 최종적으로 정해진 상태 차이와 양 끝 수분값만 출력한다. K가 1이면 선택한 한 벌의 가장 작은 수분값과 가장 큰 수분값이 같다. 따라서 상태 차이는 0이며, 동점 규칙에 따라 전체 옷 중 수분값이 가장 작은 옷을 고른다. K가 N이면 모든 옷을 골라야 한다. 입력에서는 항상 1 이상 N 이하의 K가 주어지므로 옷을 고를 수 없는 경우는 발생하지 않는다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 1 ≤ K ≤ N ≤ 100,000이다. 둘째 줄에 각 옷의 수분값을 나타내는 정수 a1, a2, …, aN이 공백으로 구분되어 주어진다. 각 값은 0 이상 1,000,000 이하이다.

출력

첫째 줄에 최소 상태 차이, 동점 규칙을 적용한 선택의 가장 작은 수분값, 가장 큰 수분값을 이 순서로 공백으로 구분하여 출력한다.

7 3
18 5 11 6 20 7 12

2 5 7

6 3
10 12 14 2 4 6

4 2 6

4 1
9 0 9 3

0 0 0

출처: Devin.KR 자체 제작