대표 관측 구간

문제

한 날씨 관측소에서는 일정한 시간 간격으로 기온을 측정한다. 관측 장치는 하루 동안 얻은 N개의 측정값을 시간순으로 배열에 저장하며, 배열의 첫 번째 값부터 차례대로 1번부터 N번까지 번호를 붙인다. 모든 측정값은 정수이며 영하의 기온은 음수로 기록한다. 장치가 정상적으로 작동했으므로 빠진 측정값은 없다. 관측소는 하루의 기록을 소개하는 안내판에 연속한 K개의 측정값을 싣기로 했다. 안내판에 실을 구간은 시작 번호 s를 정하면 s번부터 s+K-1번까지의 측정값으로 구성된다. 여기서 s는 1 이상 N-K+1 이하의 정수여야 한다. 기록의 마지막과 처음을 이어 붙일 수 없으며, 구간 안의 측정값을 건너뛰거나 순서를 바꿀 수도 없다. 안내판 담당자는 선택한 구간에 들어 있는 모든 측정값의 합을 그 구간의 대표 점수로 정한다. 음수도 부호를 그대로 유지하여 더한다. 모든 후보 구간의 길이가 K로 같으므로, 대표 점수가 가장 큰 구간을 고르면 평균 기온이 가장 높은 구간도 함께 고르게 된다. 평균값을 직접 계산하거나 반올림할 필요는 없다. 대표 점수가 가장 큰 구간이 여러 개라면 시작 번호가 가장 작은 구간을 선택한다. 즉, 같은 점수를 얻는다면 시간상 가장 먼저 나타난 구간을 안내판에 싣는다. 측정값이 모두 음수이더라도 반드시 하나의 구간을 선택해야 하며, 점수가 음수라는 이유로 빈 구간을 고를 수는 없다. K가 N이면 하루의 전체 기록이 유일한 후보가 된다. 측정값 배열과 K가 주어질 때, 선택할 구간의 시작 번호와 대표 점수를 구하는 프로그램을 작성한다. 구간의 끝 번호나 평균 기온은 출력하지 않는다.

입력

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

출력

선택할 구간의 시작 번호와 그 구간의 대표 점수를 공백으로 구분하여 한 줄에 출력한다. 시작 번호는 1부터 센다. 대표 점수가 같은 구간이 여러 개라면 시작 번호가 가장 작은 구간을 출력한다.

7 3
-2 5 1 -4 6 2 -1

5 7

5 2
-4 -2 -4 -2 -8

1 -6

1 1
0

1 0

출처: Devin.KR 자체 제작