우체국 분류대의 진동 기록

문제

한 우체국의 소포 분류대에는 일정한 시간 간격으로 진동의 크기를 기록하는 센서가 설치되어 있다. 소포가 분류대에 닿는 순간에는 주변 기록과 크게 다른 값이 잠깐 나타날 수 있다. 임베디드·데이터 담당자는 수집한 기록에 간단한 필터를 적용하고, 필터가 값을 바꾼 구간의 길이도 함께 확인하려 한다. 시간순으로 수집한 원본 센서 값은 A₁부터 Aₙ까지이다. 첫 번째 값과 마지막 값은 비교할 양쪽 이웃이 모두 존재하지 않으므로 항상 원본 그대로 둔다. 기록이 하나뿐이면 그 값 하나를 그대로 두며, 기록이 두 개이면 두 값 모두 그대로 둔다. 그 밖의 위치 i에서는 원본 값 Aᵢ₋₁, Aᵢ, Aᵢ₊₁ 세 개를 작은 순서대로 정렬했을 때 가운데에 오는 값을 Mᵢ라고 한다. 같은 값이 여러 개 있어도 세 값을 각각 하나씩 놓고 가운데 값을 선택한다. 주어진 정수 기준 T에 대해 |Aᵢ-Mᵢ|가 T보다 크면 해당 위치를 이상치로 표시하고, 필터 결과 Bᵢ를 Mᵢ로 정한다. 차이가 T와 같거나 더 작으면 이상치로 표시하지 않고 Bᵢ를 Aᵢ로 정한다. 모든 위치의 판단은 처음에 주어진 원본 배열만 사용하여 수행한다. 앞선 위치의 값을 이미 바꾸었더라도 그 바뀐 값을 다음 위치의 가운데 값 계산에 사용하지 않는다. 따라서 처리 순서는 결과에 영향을 주지 않는다. 첫 번째 위치와 마지막 위치는 이상치로 표시되지 않는다. 필터 적용 후 이상치로 표시한 위치의 개수와 모든 결과 값의 합을 구한다. 또한 원본의 시간 순서에서 이상치로 표시한 위치만 연속해서 나타나는 구간 중 가장 긴 길이를 구한다. 표시되지 않은 위치가 하나라도 사이에 있으면 서로 다른 구간이다. 이상치가 하나도 없으면 가장 긴 길이는 0이다.

입력

첫째 줄에 정수 N과 T가 공백으로 구분되어 주어진다. 1≤N≤80,000, 0≤T≤999이다.
둘째 줄에 N개의 정수 A₁, A₂, …, Aₙ이 공백으로 구분되어 주어진다. 모든 센서 값은 0 이상 999 이하이다.

출력

이상치 개수, 필터 결과 값의 합, 이상치가 연속해서 나타나는 가장 긴 구간의 길이를 이 순서대로 한 줄에 공백으로 구분하여 출력한다.

5 5
10 90 10 90 10

3 130 3

4 10
0 10 0 0

0 10 0

1 0
999

0 999 0

출처: Devin.KR 자체 제작