농장 추가 정산 구간

문제

한 농장은 수확물을 주문별로 출고하고, 매일 업무가 끝나면 재고 기록과 입금 내역을 대조한다. 주문 접수 때 계산한 예상 정산액과 실제 정산액은 다를 수 있다. 재고 부족으로 주문 일부를 취소하면 금액이 줄어들고, 대체 상품 출고를 구매자가 승인하면 금액이 늘어날 수 있다. 포장재 반환이나 출고 수량 정정도 그날의 정산에 반영된다. 백엔드 시스템은 이러한 차이를 하루에 하나의 정수로 합친다. 이 값을 일별 조정액이라고 한다. 단위는 천 원이며, 양수는 농장이 추가로 받을 금액, 음수는 농장이 돌려줄 금액이다. 0은 예상 정산액과 실제 정산액이 같다는 뜻이다. 입력으로 주어지는 조정액은 모든 주문과 재고 규칙을 이미 반영한 최종 값이므로, 개별 주문을 다시 계산할 필요는 없다. 농장은 기록된 N일 중 연속한 날짜 구간 하나를 골라 추가 정산 요청서에 넣으려 한다. 날짜에는 기록 순서대로 1번부터 N번까지 번호가 붙어 있다. 구간을 고르면 시작일부터 종료일까지의 모든 조정액을 더한 값이 요청 금액이 된다. 구간 중간의 날짜를 빼거나, 서로 떨어진 여러 구간을 합칠 수는 없다. 하루만 고르는 것도 가능하다. 요청 금액이 양수인 구간 중 금액이 가장 큰 구간을 선택한다. 금액이 같다면 포함된 날짜 수가 가장 적은 구간을 선택한다. 금액과 날짜 수가 모두 같다면 시작 날짜의 번호가 가장 작은 구간을 선택한다. 이러한 우선순위에 따라 선택되는 구간은 하나로 정해진다. 양수인 요청 금액을 만드는 구간이 없다면 요청서를 만들지 않는다. 이때는 금액과 두 날짜를 모두 0으로 기록한다. 일별 조정액을 바탕으로 요청 금액, 시작 날짜, 종료 날짜를 구하는 프로그램을 작성한다.

입력

첫째 줄에 기록된 날짜 수인 정수 N이 주어진다. (1 ≤ N ≤ 100,000)
둘째 줄에 1일부터 N일까지의 일별 조정액 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 각 조정액은 정수이며 -9 ≤ A_i ≤ 9이다.

출력

선택된 구간의 요청 금액, 시작 날짜, 종료 날짜를 공백으로 구분하여 한 줄에 출력한다. 요청 금액은 입력과 같은 천 원 단위의 정수로 출력한다. 요청 금액이 같은 경우에는 날짜 수가 적은 구간을, 날짜 수도 같은 경우에는 시작 날짜가 빠른 구간을 출력한다. 양수인 요청 금액을 만드는 구간이 없다면 0 0 0을 출력한다.

8
3 -2 4 -6 2 3 -5 5

5 8 8

5
2 2 -4 4 -9

4 4 4

6
0 -3 0 -1 -2 0

0 0 0

출처: Devin.KR 자체 제작