길이가 고른 예고편 묶음

문제

한 영화관은 상영 전에 보여 줄 예고편 묶음을 준비하고 있다. 사용할 수 있는 예고편은 N개이며, 각 예고편의 재생 시간은 초 단위의 양의 정수로 주어진다. 담당자는 이 중 정확히 K개를 골라 하나의 묶음으로 만들려고 한다. 예고편을 고르는 순서는 결과에 영향을 주지 않는다. 담당자는 묶음에 포함된 예고편들의 길이가 가능한 한 고르기를 원한다. 이를 위해 묶음의 길이 차이를 가장 긴 예고편의 재생 시간에서 가장 짧은 예고편의 재생 시간을 뺀 값으로 정의한다. 선택한 예고편이 하나뿐이거나 선택한 예고편들의 재생 시간이 모두 같으면 길이 차이는 0이다. 목표는 정확히 K개를 선택했을 때 이 길이 차이를 최소로 만드는 것이다. 최소 길이 차이를 만드는 묶음이 여러 개라면, 그중 가장 짧은 예고편의 재생 시간이 더 작은 묶음을 기준으로 삼는다. 길이 차이와 가장 짧은 재생 시간이 모두 같으면 가장 긴 재생 시간도 같으므로 더 이상의 동점 처리는 필요하지 않다. 실제로 어떤 예고편을 골랐는지나 예고편의 원래 번호는 출력하지 않는다. 재생 시간이 같은 예고편도 서로 다른 예고편이다. 따라서 같은 재생 시간이 여러 번 입력되면 그 개수만큼 선택할 수 있다. 다만 하나의 예고편을 두 번 선택할 수는 없다. 예고편을 잘라 재생 시간을 바꾸거나 여러 예고편을 합쳐 하나로 세는 일도 허용되지 않는다. 입력은 예고편이 등록된 순서대로 주어지며, 재생 시간의 크기순으로 정렬되어 있다는 보장은 없다. 항상 1개 이상 N개 이하의 예고편을 고르므로 선택할 수 없는 경우는 없다. 정해진 기준에 따른 최소 길이 차이와, 기준으로 삼은 묶음의 가장 짧은 재생 시간 및 가장 긴 재생 시간을 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 1 ≤ K ≤ N ≤ 100,000이다. 다음 N개 줄에 각 예고편의 재생 시간 D_i가 하나씩 주어진다. 모든 D_i는 정수이며 1 ≤ D_i ≤ 999다.

출력

최소 길이 차이, 동점 처리 기준에 따라 정한 묶음의 가장 짧은 재생 시간, 가장 긴 재생 시간을 이 순서대로 한 줄에 공백으로 구분하여 출력한다.

6 3
18
10
13
11
19
12

2 10 12

5 3
24
7
24
24
8

0 24 24

4 1
9
3
6
3

0 3 3

출처: Devin.KR 자체 제작