영화관 센서의 안정 구간

문제

한 영화관은 상영관의 환경을 점검하기 위해 일정한 시간 간격으로 센서 값을 기록한다. 센서 값은 기준 온도와의 차이를 정수로 나타낸 것으로, 음수도 나올 수 있다. 데이터 담당자는 시간순으로 모인 N개의 측정값에서 일시적인 이상치를 표시하고, 이상치 없이 연속해서 측정된 가장 긴 구간을 보고하려 한다. 측정 기록의 번호는 시간순으로 1부터 N까지다. 먼저 전체 측정값을 오름차순으로 정렬했을 때 앞에서 ⌊(N+1)/2⌋번째에 있는 값을 기준값 M으로 정한다. 여기서 ⌊x⌋는 x 이하인 가장 큰 정수다. 따라서 N이 짝수이면 가운데 두 값 중 작은 값을 사용한다. 같은 값이 여러 번 나타나면 각각 별개의 원소로 취급한다. 정렬은 기준값을 정할 때만 사용하며, 측정 기록의 원래 시간 순서는 바꾸지 않는다. 허용 차이 D가 주어졌을 때, 측정값 X가 |X-M| ≤ D를 만족하면 정상이고 그렇지 않으면 이상치다. 차이가 정확히 D인 값도 정상에 포함한다. 이상치를 표시한 뒤 기준값을 다시 계산하지는 않는다. 모든 기록의 정상 여부는 처음 구한 하나의 기준값으로 결정한다. 안정 구간은 원래 기록에서 연속한 하나 이상의 측정으로 이루어지고, 포함된 모든 측정이 정상인 구간이다. 가장 긴 안정 구간을 찾아 그 길이와 양 끝 기록 번호를 보고하라. 길이가 같은 구간이 여러 개라면 시작 기록 번호가 가장 작은 구간을 선택한다. 기준값 M과 같은 측정값은 반드시 존재하고 D는 음수가 아니므로 안정 구간은 항상 존재한다. 이상치의 총개수도 함께 구한다.

입력

첫째 줄에 정수 N과 D가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 100,000이고 0 ≤ D ≤ 20이다.
둘째 줄에 시간순 측정값 X_1, X_2, …, X_N이 공백으로 구분되어 주어진다. 각 X_i는 -9 이상 9 이하인 정수다.

출력

첫째 줄에 기준값 M과 이상치의 총개수를 공백으로 구분하여 출력한다. 둘째 줄에 가장 긴 안정 구간의 길이, 시작 기록 번호, 끝 기록 번호를 공백으로 구분하여 출력한다. 최대 길이가 같으면 시작 기록 번호가 가장 작은 구간을 출력한다.

8 1
2 3 8 2 1 3 -4 2

2 2
3 4 6

6 0
-2 4 -2 4 -2 4

-2 3
1 1 1

1 0
9

9 0
1 1 1

출처: Devin.KR 자체 제작