처음과 같은 적재량

문제

공유 자전거를 관리하는 작업 차량에 오늘 처리할 요청 N개가 도착했다. 요청은 도착한 순서대로 1번부터 N번까지 번호가 붙어 있으며, 각 요청은 자전거 한 대를 회수하거나 배치하는 작업이다. 회수 요청의 기록은 1이고, 배치 요청의 기록은 -1이다. 회수하면 차량에 실린 자전거가 한 대 늘어나고, 배치하면 한 대 줄어든다. 관리자는 연속한 요청 일부를 하나의 작업 묶음으로 지정하려 한다. 묶음은 두 정수 L과 R을 골라 L번부터 R번까지의 요청을 모두 포함한다. 이때 1 ≤ L ≤ R ≤ N이어야 하며, 중간 요청을 빼거나 요청의 순서를 바꿀 수 없다. 묶음에 포함되지 않은 요청은 다른 작업 시간에 처리하므로 이번 묶음의 적재량 변화에 영향을 주지 않는다. 작업 차량은 묶음을 시작할 때 자전거 N대를 싣고 있으며, 최대 2N대까지 실을 수 있다. 따라서 어떤 묶음을 고르더라도 작업 도중 자전거가 부족하거나 적재 한도를 넘는 일은 없다. 요청 사이의 이동 거리와 작업 시간도 묶음을 고르는 조건에 포함하지 않는다. 관리자가 원하는 묶음은 첫 요청을 처리하기 직전과 마지막 요청을 처리한 직후에 차량에 실린 자전거 수가 같은 묶음이다. 즉, 묶음 안에서 회수한 자전거 수와 배치한 자전거 수가 정확히 같아야 한다. 작업 도중의 적재량은 시작할 때와 달라도 된다. 조건을 만족하는 묶음 중 포함된 요청 수 R-L+1이 가장 큰 것을 구한다. 가장 긴 묶음이 여러 개라면 시작 번호 L이 가장 작은 것을 선택한다. 길이가 같고 시작 번호도 같으면 끝 번호 역시 같으므로 추가 동점 규칙은 필요하지 않다. 요청을 하나도 포함하지 않는 묶음은 선택할 수 없다. 조건을 만족하는 묶음이 하나도 없다면 정해진 형식으로 없음을 출력한다.

입력

첫째 줄에 요청 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 100,000이다.
둘째 줄에 각 요청의 기록을 나타내는 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 모든 i에 대해 A_i는 1 또는 -1이다.

출력

선택한 묶음의 요청 수, 시작 번호 L, 끝 번호 R을 공백으로 구분하여 한 줄에 출력한다. 조건을 만족하는 묶음이 없다면 0 0 0을 출력한다.

9
1 1 -1 -1 1 1 -1 -1 1

8 1 8

7
1 1 1 -1 1 -1 1

4 3 6

3
-1 -1 -1

0 0 0

출처: Devin.KR 자체 제작