재활용

헥 S. 퀸시(친구들은 그를 Hex라고 부른다)는 Tri-state 광역권에 속한 Quad Cities와 Lone Star State의 Twin Cities에서 재활용 사업을 총괄한다. 그가 맡은 프로그램 중 하나는 도시 곳곳에 대형 재활용 수거함을 설치하는 것이다. 수거함을 옮기는 데 비용이 많이 들기 때문에, 그는 수거함을 한 장소에 가능한 오래 두고 일주일에 한 번씩 비운다. 매주 말에 수거함이 가득 차 있는 한 그 장소에 수거함을 계속 둔다.

헥은 장소마다 매주 나올 재활용 물질의 양(세제곱미터)을 꽤 정확하게 예측하고 있다. 이 예측을 바탕으로 회수량을 최대로 만들 수거함의 크기와 설치 시점을 알고 싶어 한다. 그는 수거함을 해당 장소에 두되, 용량을 채우지 못할 것으로 예상되는 첫 주의 직전 주까지만 둔다.

예를 들어 앞으로 7주 동안의 예상치가 $2\ 5\ 7\ 3\ 5\ 10\ 2$라고 하자. 헥에게는 다음과 같은 선택지가 있다.

• 용량 2인 수거함을 1주차부터 7주차까지 두면 $14\textrm{m}^3$를 재활용한다
• 용량 5인 수거함을 2주차부터 3주차까지 두면 $10\textrm{m}^3$를 재활용한다
• 용량 3인 수거함을 2주차부터 6주차까지 두면 $15\textrm{m}^3$를 재활용한다(가능한 최댓값이다)

용량 5인 수거함을 2주차부터 6주차까지 두지는 않는다. 4주차에 가득 차지 않기 때문이다.

첫 줄에 예상치가 있는 주의 수를 나타내는 양의 정수 $n$ ($n \leq 100\,000$)이 하나 주어진다. 주는 1번부터 $n$번까지 번호가 매겨진다. 이어지는 $n$개의 정수는 각 주에 예상되는 재활용량을 순서대로 나타내는 음이 아닌 정수이다. 이 값들은 여러 줄에 걸쳐 주어질 수 있다.

세 정수 $s$ $e$ $r$을 출력한다. $s$와 $e$는 수거함을 설치할 시작 주와 끝 주이고, $r$은 재활용량 합계의 최댓값이다. 같은 최댓값을 내는 기간이 둘 이상이면 $s$가 가장 작은 기간을 출력한다.

모호한 테스트 케이스가 하나 있다. 이 테스트 케이스는 zip 파일에 포함되어 있지 않다. 가능한 답은 다음 두 가지이다.

• 1 50000 2500050000
• 1 50001 2500050000