함께 검토할 관측값

문제

날씨 관측소는 하루 동안 모인 온도 관측 기록 가운데 정확히 K개를 골라 하나의 검토 묶음을 만들려고 한다. 각 기록에는 정수로 표현한 온도 하나가 적혀 있다. 서로 다른 기록에 같은 온도가 적혀 있을 수 있으며, 이 경우에도 각 기록은 별개의 기록으로 취급한다. 기록이 입력된 순서는 관측 장치가 자료를 전송한 순서일 뿐이므로, 묶음을 만들 때 입력에서 연속한 기록을 고를 필요는 없다. 검토 담당자는 온도 차이가 작은 기록들을 함께 살펴보려고 한다. 선택한 K개 기록의 최솟값을 L, 최댓값을 H라고 할 때, 그 묶음의 폭은 H-L이다. 관측소는 가능한 모든 선택 중 폭이 가장 작은 묶음을 사용한다. 폭이 같은 묶음이 여러 개라면 L이 가장 작은 묶음을 사용한다. 이 두 조건까지 같은 묶음들은 어떤 기록을 포함하는지와 관계없이 같은 결과로 취급한다. 같은 온도를 가진 기록을 여러 개 선택해도 되지만, 입력에 등장한 한 기록을 두 번 선택할 수는 없다. 예를 들어 어떤 온도가 세 번 등장했다면 그 온도의 기록은 최대 세 개까지 사용할 수 있다. K가 1이면 모든 묶음의 폭은 0이므로, 동점 처리 규칙에 따라 전체 기록 중 가장 낮은 온도를 가진 기록을 선택하게 된다. K가 N이면 모든 기록을 선택해야 한다. 관측소가 최종적으로 사용할 묶음의 L과 H를 구하는 프로그램을 작성한다. 기록의 번호나 선택한 기록 전체를 출력할 필요는 없다. K는 항상 전체 기록 수 이하이므로 유효한 묶음은 반드시 존재하며, 정해진 동점 처리 규칙에 의해 출력할 두 온도는 하나로 결정된다.

입력

첫째 줄에 정수 N과 K가 공백으로 주어진다. 1≤K≤N≤100,000이다.
둘째 줄에 N개 기록의 온도 A_1, A_2, …, A_N이 공백으로 주어진다. 모든 A_i는 정수이며 0≤A_i≤99이다.

출력

선택한 묶음의 최솟값 L과 최댓값 H를 공백으로 구분하여 한 줄에 출력한다.

7 3
8 2 9 3 15 4 10

2 4

4 2
6 6 1 9

6 6

3 1
7 0 5

0 0

출처: Devin.KR 자체 제작