동기화 묶음

문제

한 게임 서버는 여러 작업 장치가 보내온 동기화 기록을 한꺼번에 정리한다. 각 기록에는 동기화를 시작한 시각이 정수로 적혀 있다. 기록은 서버에 도착한 순서로 저장되어 있으므로, 입력에 적힌 시각이 시간순이라는 보장은 없다. 서로 다른 기록에 같은 시각이 적혀 있을 수도 있으며, 이 경우에도 각각을 별개의 기록으로 센다. 서버는 먼저 모든 기록을 시작 시각의 오름차순으로 정렬한다. 그런 다음 첫 기록부터 차례로 살펴보며 동기화 묶음을 만든다. 첫 기록은 첫 묶음에 넣는다. 두 번째 기록부터는 바로 앞 기록과의 시각 차이가 D 이하이면 바로 앞 기록이 속한 묶음에 넣고, D보다 크면 새로운 묶음을 시작한다. 따라서 하나의 묶음 안에서 가장 이른 시각과 가장 늦은 시각의 차이가 D보다 클 수도 있다. 묶음의 경계는 정렬한 뒤 서로 이웃한 두 기록의 차이만으로 결정된다. 예를 들어 D가 3이고 정렬한 시각이 2, 5, 8이라면, 이웃한 시각의 차이가 모두 3이므로 세 기록은 하나의 묶음에 들어간다. 반면 시각이 2, 5, 9라면 5와 9 사이에서 새로운 묶음이 시작된다. 같은 시각의 기록 사이에는 차이가 없으므로 항상 같은 묶음에 들어간다. 운영자는 만들어진 묶음의 총개수와, 가장 많은 기록을 포함하는 묶음의 정보를 알고 싶다. 기록 수가 가장 많은 묶음이 여러 개라면 가장 이른 시작 시각을 가진 묶음을 선택한다. 선택한 묶음에 대해 가장 이른 시각, 가장 늦은 시각, 포함된 기록 수를 구한다. 기록은 하나 이상 주어지므로 묶음은 반드시 하나 이상 만들어진다.

입력

첫째 줄에 기록 수 N과 기준 차이 D가 공백으로 구분되어 주어진다. N과 D는 정수이며 1 ≤ N ≤ 50,000, 0 ≤ D ≤ 99,999이다.
둘째 줄에 각 기록의 시작 시각을 나타내는 정수 N개가 공백으로 구분되어 주어진다. 각 시각은 0 이상 99,999 이하이다. 같은 시각이 여러 번 주어질 수 있다.

출력

첫째 줄에 만들어진 묶음의 총개수를 출력한다. 둘째 줄에 선택한 묶음의 가장 이른 시각, 가장 늦은 시각, 기록 수를 이 순서대로 공백으로 구분하여 출력한다. 최대 기록 수가 같은 묶음이 여러 개라면 가장 이른 시각이 작은 묶음을 선택한다.

8 4
18 3 8 4 22 14 8 30

3
3 8 4

6 0
5 2 5 9 2 5

3
5 5 3

4 3
10 1 7 4

1
1 10 4

출처: Devin.KR 자체 제작