자전거가 넉넉했던 연속 기록

문제

공유 자전거 보관소에서는 일정한 간격으로 보관 중인 자전거 수를 확인한다. 관리자는 이용자가 자전거를 빌리기 편했던 시간을 살펴보기 위해, 자전거가 기준 대수 이상 남아 있던 점검이 얼마나 오래 연속되었는지 조사하려 한다. 여기서 연속된다는 것은 점검 번호가 하나씩 이어진다는 뜻이며, 실제 시간의 길이를 따로 계산하지는 않는다. 첫 점검 전 보관소에는 S대의 자전거가 있다. 각 점검 기록에는 바로 이전 상태와 비교해 자전거 수가 얼마나 변했는지만 적혀 있다. 첫 번째 기록은 관찰 시작 시점부터 첫 점검까지의 변화량이고, 두 번째 이후의 기록은 직전 점검부터 이번 점검까지의 변화량이다. 양수는 반납 등으로 자전거가 늘었음을 뜻하고, 음수는 대여 등으로 줄었음을 뜻한다. 변화량이 0인 기록도 있을 수 있다. 점검 결과를 판단할 때에는 반드시 해당 기록의 변화량을 먼저 반영한다. 그렇게 얻은 자전거 수가 기준 K 이상이면 그 점검을 충분한 점검이라고 부른다. 자전거 수가 정확히 K인 경우도 포함한다. 관찰 시작 시점의 S 자체는 점검 기록이 아니므로 연속 길이에 포함하지 않는다. 입력은 모든 변화량을 순서대로 반영했을 때 자전거 수가 음수가 되지 않도록 주어진다. 관리자가 찾는 것은 충분한 점검만으로 이루어진 가장 긴 연속 구간이다. 중간에 자전거 수가 K보다 적은 점검이 한 번이라도 있으면 그 앞뒤를 하나의 구간으로 합칠 수 없다. 길이가 같은 최장 구간이 여러 개라면 시작 점검 번호가 가장 작은 구간을 선택한다. 점검 번호는 1번부터 시작한다. 선택한 구간의 길이와 시작 점검 번호를 구한다. 충분한 점검이 하나도 없다면 선택할 구간이 없으므로 두 값 모두 0으로 정한다.

입력

첫째 줄에 점검 수 N, 관찰 시작 시점의 자전거 수 S, 기준 대수 K가 주어진다. N은 1 이상 100,000 이하, S는 0 이상 1,000,000 이하, K는 1 이상 2,000,000 이하의 정수다.
다음 N개의 줄에 각 점검의 변화량 D가 하나씩 주어진다. D는 -9 이상 9 이하의 정수다. 모든 접두 구간에 대해 S에 해당 구간의 변화량 합을 더한 값이 0 이상임이 보장된다.

출력

선택한 연속 구간의 길이와 시작 점검 번호를 공백으로 구분하여 출력한다. 충분한 점검이 하나도 없다면 0 0을 출력한다.

7 3 5
2
0
-1
2
-1
0
-3

3 4

6 2 3
1
0
-1
1
0
-1

2 1

3 0 4
1
1
1

0 0

출처: Devin.KR 자체 제작