캠핑장의 두 안내등

문제

캠핑장에는 일직선 산책로를 따라 1번부터 L번까지의 구역이 차례로 놓여 있다. 캠핑장 관리자는 밤에도 이용객이 자기 텐트를 쉽게 찾도록 서로 다른 두 구역에 안내등을 하나씩 설치하려 한다. 안내등을 설치할 수 있는 위치는 구역 번호로만 나타내며, 텐트가 있는 구역에도 안내등을 설치할 수 있다. 두 안내등은 반드시 설치해야 하며, 같은 구역에 두 안내등을 놓을 수는 없다. 모든 안내등의 밝기는 같고, 안내등이 설치된 구역과 번호 차이가 R 이하인 구역을 비춘다. 따라서 a번 구역에 설치한 안내등은 번호가 x인 구역에 대해 |x-a|가 R 이하일 때 그 구역을 비춘다. 산책로 양쪽 끝을 넘어가는 범위는 무시한다. 끝 구역과 처음 구역은 이어져 있지 않으며, 구역 번호의 차이를 그대로 거리로 사용한다. R이 0이면 안내등이 설치된 구역만 밝아진다. 캠핑장에는 N개의 텐트가 있다. 각 텐트가 속한 구역은 입력으로 주어지며, 같은 구역에 여러 텐트가 있을 수 있다. 어느 한 안내등이라도 텐트가 속한 구역을 비추면 그 텐트는 밝아진 텐트로 센다. 두 안내등이 모두 비추는 텐트도 한 번만 센다. 한 구역에 텐트가 여러 개 있다면 그 구역이 밝아질 때 해당 텐트를 모두 센다. 텐트의 입력 순서는 설치 위치를 고르는 데 영향을 주지 않는다. 관리자는 밝아지는 텐트 수가 가장 많아지도록 두 위치를 고른다. 선택한 두 구역을 a<b가 되도록 적었을 때, 최댓값을 만드는 선택이 여러 개라면 a가 가장 작은 선택을 고른다. a까지 같다면 b가 가장 작은 선택을 고른다. 텐트가 하나도 없어도 같은 기준으로 두 위치를 고른다. 설치할 두 구역과 그때 밝아지는 텐트 수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 L, N, R이 공백으로 구분되어 주어진다. 2≤L≤60, 0≤N≤100,000, 0≤R≤L이다.
둘째 줄에 각 텐트가 속한 구역 번호를 나타내는 N개의 정수 x가 공백으로 구분되어 주어진다. 각 x는 1≤x≤L을 만족한다. N이 0이면 둘째 줄은 빈 줄이다.

출력

선택한 두 구역 a, b와 밝아지는 텐트 수를 이 순서대로 한 줄에 공백으로 구분하여 출력한다. 반드시 a<b여야 한다. 밝아지는 텐트 수를 최대로 하고, 동점이면 a가 작은 선택, 그다음 b가 작은 선택을 출력한다.

6 5 1
1 2 4 4 6

1 5 5

4 0 0

1 2 0

5 6 0
3 3 3 5 5 1

3 5 5

출처: Devin.KR 자체 제작