연속 날짜의 택배 보관 기록

문제

택배 보관소는 지난 N일 동안 날짜별로 들어온 택배의 개수를 기록했다. 기록의 첫 날짜를 1일, 마지막 날짜를 N일이라고 부른다. 관리자는 이 기록을 이용하여 임시 보관함의 크기를 검토하려 한다. 임시 보관함에는 택배를 최대 K개까지 넣을 수 있으며, 모든 택배는 같은 크기의 보관 공간 하나를 차지한다. 검토할 때는 실제로 택배를 옮기는 대신, 기록에서 비어 있지 않은 연속 날짜 구간 하나를 선택한다. 선택한 첫 날짜부터 마지막 날짜까지 들어온 택배를 모두 임시 보관함에 넣는다고 가정한다. 이 가정에서는 선택한 구간이 끝날 때까지 택배를 하나도 꺼내지 않는다. 선택한 날짜 가운데 일부의 택배만 넣거나 중간 날짜의 기록을 건너뛸 수는 없다. 따라서 필요한 보관 공간은 선택한 구간에 기록된 택배 수의 합과 같다. 관리자가 원하는 구간은 필요한 보관 공간이 K개 이하인 구간이다. 보관함을 정확히 채울 필요는 없으며 일부 공간이 남아도 된다. 택배가 한 개도 들어오지 않은 날짜도 기록에 포함되어 있고, 이런 날짜를 선택해도 보관 공간은 늘어나지 않는다. 다만 택배가 없는 날짜 역시 선택한 구간의 날짜 수에는 포함된다. K가 0일 때도 같은 규칙을 적용한다. 관리자는 조건을 만족하는 구간 가운데 날짜 수가 가장 많은 구간을 찾으려 한다. 가장 긴 구간이 여러 개라면 시작 날짜가 가장 이른 구간을 선택한다. 기록에 적힌 날짜 순서는 바꿀 수 없고, 첫 날짜와 마지막 날짜를 이어 붙여 순환하는 구간을 만들 수도 없다. 선택한 구간의 날짜 수와 시작 날짜를 구한다. 하루짜리 구간조차 조건을 만족하지 못하는 경우에는 별도로 정한 두 값을 출력한다.

입력

첫째 줄에 정수 N과 K가 공백으로 주어진다. 1 ≤ N ≤ 50,000이며 0 ≤ K ≤ 50,000,000이다.
둘째 줄에 날짜별 택배 수 A_1, A_2, …, A_N이 공백으로 주어진다. 모든 A_i는 정수이며 0 ≤ A_i ≤ 999이다.

출력

선택한 구간의 날짜 수와 시작 날짜를 이 순서대로 한 줄에 공백으로 구분하여 출력한다. 최대 길이 구간이 여러 개면 시작 날짜가 가장 이른 것을 출력한다. 조건을 만족하는 비어 있지 않은 구간이 없으면 0 0을 출력한다.

7 6
2 1 3 0 4 1 1

4 1

4 0
1 2 3 4

0 0

6 0
2 0 0 3 0 0

2 2

출처: Devin.KR 자체 제작