천문대 센서의 잡음 구간

문제

한 천문대에서는 망원경의 관측 환경을 점검하기 위해 센서가 일정한 시간 간격으로 보낸 값을 저장한다. 센서 값은 장치 내부에서 0 이상 99 이하의 정수로 변환된다. 데이터 담당자는 한 번의 관측에서 수집한 N개의 값을 받아 이상치를 표시하고, 장치 점검에 사용할 대표 잡음 구간을 고르려 한다. 각 값에는 수집된 순서대로 1번부터 N번까지 번호가 붙어 있다. 이번 점검에서는 관측 전체의 중앙값을 기준으로 이상치를 판정한다. 입력된 N개의 값을 오름차순으로 정렬했을 때, 앞에서부터 ⌊(N+1)/2⌋번째에 있는 값을 기준값 M으로 정한다. 여기서 ⌊x⌋는 x 이하인 가장 큰 정수다. 따라서 N이 짝수이면 가운데 두 값 중 작은 값을 사용한다. 기준값을 구할 때 같은 값도 각각 하나의 값으로 센다. 허용 차이 D가 주어졌을 때, 번호 i의 센서 값과 M의 차이의 절댓값이 D보다 크면 그 값을 이상치로 표시한다. 차이가 정확히 D인 값은 정상이다. 기준값은 처음 받은 모든 값으로 한 번만 계산하며, 이상치를 표시한 뒤 다시 계산하지 않는다. 정렬은 기준값을 정하는 데에만 사용하고, 잡음 구간은 반드시 원래 수집 순서에서 찾는다. 잡음 구간은 하나 이상의 연속한 번호로 이루어지며, 구간 안의 모든 값이 이상치인 구간이다. 천문대는 가장 많은 값을 포함하는 잡음 구간 하나를 대표 구간으로 기록한다. 길이가 같은 후보가 여러 개라면 시작 번호가 가장 작은 구간을 고른다. 정상인 값을 사이에 둔 두 구간을 하나로 합칠 수는 없다. 전체 이상치의 개수와 대표 구간의 시작 번호 및 끝 번호를 구하는 프로그램을 작성한다. 이상치가 하나도 없다면 전체 이상치의 개수는 0이고, 대표 구간의 시작 번호와 끝 번호도 모두 0으로 기록한다. 센서 값을 실제로 삭제하거나 정상인 값의 순서를 바꾸는 작업은 수행하지 않는다.

입력

첫째 줄에 센서 값의 개수 N과 허용 차이 D가 공백으로 구분되어 주어진다. N과 D는 정수이며 1 ≤ N ≤ 100,000, 0 ≤ D ≤ 99다.
둘째 줄에 수집 순서대로 센서 값 A₁, A₂, …, Aₙ이 공백으로 구분되어 주어진다. 모든 Aᵢ는 0 이상 99 이하의 정수다.

출력

첫째 줄에 전체 이상치의 개수 K를 출력한다. 둘째 줄에 대표 잡음 구간의 시작 번호 L과 끝 번호 R을 공백으로 구분하여 출력한다. 가장 긴 구간이 여러 개라면 시작 번호가 가장 작은 구간을 출력한다. K가 0이면 둘째 줄에 0 0을 출력한다.

9 2
10 11 50 49 10 9 60 61 10

4
3 4

4 0
5 8 5 8

2
2 2

1 0
0

0
0 0

출처: Devin.KR 자체 제작