은행 창구의 묶음 상담

문제

한 은행은 영업을 시작하기 전에 특별 상담 창구에서 함께 안내할 고객들을 정한다. 오늘 상담을 신청한 고객은 N명이며, 각 고객의 상담 예상 시간은 정수 분 단위로 기록되어 있다. 예상 시간이 비슷한 고객을 모으면 공통 안내를 준비하기 쉬우므로, 은행은 신청자 중 정확히 K명을 골라 하나의 상담 묶음을 만들려고 한다. 선택한 고객들의 상담 예상 시간 중 가장 작은 값을 L, 가장 큰 값을 R이라고 하자. 은행은 R-L을 그 묶음의 시간 차이라고 부른다. 시간 차이가 허용값 D 이하인 묶음만 실제 상담에 사용할 수 있다. 고객이 신청한 순서는 선택에 영향을 주지 않으며, 신청 명단에서 서로 떨어져 있는 고객들을 함께 골라도 된다. 예상 시간이 같은 고객도 각각 별개의 신청자이므로, 같은 시간이 여러 번 등장하면 그 횟수만큼 선택할 수 있다. 사용할 수 있는 묶음이 여러 개라면 시간 차이 R-L이 가장 작은 묶음을 선택한다. 시간 차이까지 같다면 가장 작은 예상 시간 L이 더 작은 묶음을 선택한다. 이 두 조건이 모두 같으면 어떤 고객들을 선택했는지는 구별하지 않는다. 따라서 선택된 고객의 번호나 신청 순서를 출력할 필요는 없다. 조건을 만족하는 최종 묶음의 L과 R만 구하면 된다. 예를 들어 정확히 한 명을 고르는 경우에는 선택한 고객의 예상 시간이 곧 L과 R이므로 시간 차이는 0이다. 또한 예상 시간이 같은 고객이 충분히 많다면 여러 명을 고르더라도 시간 차이가 0일 수 있다. 다만 허용값을 만족하는 묶음이 전혀 없다면 상담 묶음을 만들 수 없다. 신청 명단과 K, D가 주어질 때, 위 규칙에 따라 선택한 묶음의 가장 작은 예상 시간과 가장 큰 예상 시간을 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, K, D가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 100,000, 1 ≤ K ≤ N, 0 ≤ D ≤ 98이다.
둘째 줄에 각 고객의 상담 예상 시간을 나타내는 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 모든 i에 대해 1 ≤ A_i ≤ 99이다.

출력

허용값을 만족하는 묶음이 있으면, 시간 차이가 최소이고 그중 L이 최소인 묶음의 L과 R을 공백으로 구분하여 한 줄에 출력한다. 허용값을 만족하는 묶음이 없으면 -1만 출력한다.

7 4 3
12 7 9 18 8 13 7

7 9

4 3 4
1 4 7 10

-1

6 2 0
5 3 5 3 8 8

3 3

출처: Devin.KR 자체 제작