택배 진동 기록 점검

문제

택배 분류장의 임베디드 장치는 상자가 이동하는 동안 진동 센서 값을 일정한 간격으로 기록한다. 한 번의 점검에서는 같은 운반 구간에서 얻은 N개의 기록을 사용한다. 기록에는 측정한 순서대로 1번부터 N번까지 번호가 붙는다. 센서 값은 0 이상 999 이하의 정수이며, 같은 값이 여러 번 나타날 수 있다. 데이터 담당자는 이번 기록의 기준값을 구한 뒤, 기준값에서 지나치게 멀어진 기록을 이상 기록으로 분류하려 한다. 기준값 M은 N개의 센서 값을 오름차순으로 정렬했을 때 아래쪽 중앙에 놓이는 값이다. 정확히는 정렬한 값에 1번부터 번호를 붙였을 때, N이 홀수이면 (N+1)/2번째 값이고 N이 짝수이면 N/2번째 값이다. 정렬은 기준값을 정하는 데에만 사용하며, 이후 기록을 살펴볼 때는 처음 입력된 측정 순서를 그대로 사용한다. 허용 차이 D가 주어진다. 어떤 기록의 센서 값을 x라고 할 때, |x-M|이 D보다 크면 그 기록은 이상 기록이다. 차이가 정확히 D인 기록은 이상 기록이 아니다. 기준값은 이상 기록을 제거하기 전의 전체 기록으로 한 번만 계산하며, 분류 도중에 다시 계산하지 않는다. 담당자는 이상 기록의 전체 개수와 이상 기록이 가장 길게 이어진 구간을 함께 확인하려 한다. 구간은 원래 측정 순서에서 번호가 연속한 기록들로 이루어지며, 구간에 포함된 모든 기록이 이상 기록이어야 한다. 가장 긴 구간이 여러 개이면 시작 번호가 가장 작은 구간을 선택한다. 이상 기록이 하나도 없으면 선택할 구간이 없으므로 시작 번호와 끝 번호를 모두 0으로 나타낸다. 센서 기록과 허용 차이가 주어질 때, 기준값과 이상 기록의 전체 개수, 선택한 구간의 시작 번호와 끝 번호를 구하는 프로그램을 작성한다.

입력

첫째 줄에 기록의 개수 N과 허용 차이 D가 공백으로 구분되어 주어진다. N과 D는 정수이며 1≤N≤80,000, 0≤D≤999이다.
둘째 줄에 측정 순서대로 센서 값 N개가 공백으로 구분되어 주어진다. 각 센서 값은 0 이상 999 이하의 정수이다.

출력

첫째 줄에 기준값 M과 이상 기록의 전체 개수를 공백으로 구분하여 출력한다. 둘째 줄에 가장 긴 이상 기록 구간의 시작 번호와 끝 번호를 공백으로 구분하여 출력한다. 길이가 같으면 시작 번호가 가장 작은 구간을 출력한다. 이상 기록이 없으면 둘째 줄에 0 0을 출력한다.

7 4
10 12 40 41 11 9 30

12 3
3 4

6 0
5 8 5 5 8 5

5 2
2 2

1 999
0

0 0
0 0

출처: Devin.KR 자체 제작