수조 관측 구간 정제

문제

수족관의 데이터 담당자는 한 수조에서 시간순으로 수집한 관측값을 정제하고 있다. 관측값은 모두 정수이며, 각 관측에는 수집된 순서에 따라 1번부터 N번까지 번호가 붙어 있다. 장비가 보내는 값 중에는 정상적인 측정값뿐 아니라 통신 오류를 나타내는 값도 섞여 있다. 담당자는 정수 L과 R을 정하고, 값이 L 이상 R 이하인 관측을 정상 관측으로 판정한다. 이 범위를 벗어난 관측은 모두 오류 관측으로 판정한다. 범위의 양 끝인 L과 R은 정상 값에 포함된다. 분석에 사용할 자료는 원본에서 연속한 하나의 구간을 골라 만든다. 구간을 고른 뒤에는 그 안의 오류 관측을 모두 삭제하고 정상 관측만 원래 순서대로 남긴다. 다만 한 번의 정제 작업에서 삭제할 수 있는 오류 관측은 최대 K개다. 따라서 선택한 원본 구간에 오류 관측이 K개보다 많이 들어 있으면 그 구간은 사용할 수 없다. 정상 관측은 삭제하지 않으며, 오류 관측의 값을 다른 값으로 바꾸는 작업도 허용하지 않는다. 담당자는 사용할 수 있는 구간 중 원본에서 차지하는 길이가 가장 긴 구간을 원한다. 여기서 길이는 정제 후 남은 관측 수가 아니라 선택한 원본 구간의 관측 수다. 예를 들어 정상 관측 세 개와 오류 관측 한 개가 들어 있는 구간의 길이는 4다. 길이가 같은 구간이 여러 개라면 시작 번호가 가장 작은 구간을 선택한다. 길이와 시작 번호가 같으면 끝 번호도 같으므로 추가 동점 규칙은 필요하지 않다. 선택하는 구간은 비어 있으면 안 된다. 오류 관측만 들어 있는 구간도 오류 개수 조건을 만족하면 선택할 수 있다. 조건을 만족하는 비어 있지 않은 구간이 전혀 없을 수도 있다. 주어진 관측 기록에 대해 선택해야 할 구간의 길이, 시작 번호, 끝 번호를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, K, L, R이 공백으로 구분되어 주어진다. 1≤N≤60,000, 0≤K≤N, 0≤L≤R≤100이다.
둘째 줄에 시간순 관측값 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 각 A_i는 -1 이상 101 이하의 정수다.

출력

조건에 따라 선택한 구간의 길이, 시작 번호, 끝 번호를 한 줄에 공백으로 구분하여 출력한다. 선택할 수 있는 비어 있지 않은 구간이 없으면 0 0 0을 출력한다.

8 1 10 20
12 3 15 18 30 11 14 16

6 3 8

5 0 4 7
4 8 5 9 7

1 1 1

3 0 10 20
-1 0 101

0 0 0

출처: Devin.KR 자체 제작