순환 노선 출발점

문제

한 도시의 순환 버스 노선에는 정류장이 1번부터 N번까지 원형으로 놓여 있고, N번 정류장 다음은 다시 1번 정류장이다. 버스는 빈 채로 어느 한 정류장 s에서 운행을 시작하여 s, s+1, …, N, 1, …, s-1번 순서로 모든 정류장을 정확히 한 번씩 정차하며 한 바퀴를 돈다. i번 정류장에서는 승차 인원에서 하차 인원을 뺀 값이 a_i이다. 즉 정차를 마치면 버스 안의 승객 수가 a_i만큼 변한다(음수이면 줄어든다). 하차하려는 승객은 이미 버스에 타고 있어야 하므로, 어느 정류장에서든 정차를 마친 뒤의 승객 수가 0보다 작아지면 그 출발 정류장은 운행할 수 없다. 출발 정류장 s의 정차도 첫 번째 정차로 계산한다. 운행이 가능한 출발 정류장이 모두 몇 개인지, 그중 번호가 가장 작은 것은 몇 번인지 구하시오. 모든 출발 정류장을 하나씩 시험해 보면 되지만 N이 크므로 정류장마다 한 바퀴를 새로 돌면 시간이 부족하다. 누적 합을 이용해 각 출발 정류장을 빠르게 판정해야 한다.

입력

첫 줄에 N, 둘째 줄에 a_1 … a_N 이 공백으로 구분되어 주어진다. 1 ≤ N ≤ 200,000, −10^9 ≤ a_i ≤ 10^9, 모든 값은 정수이다.

출력

운행 가능한 출발 정류장의 개수와 그중 가장 작은 번호를 공백으로 구분해 한 줄에 출력한다. 가능한 출발 정류장이 없으면 0 -1 을 출력한다.

5
2 -3 1 -1 3

2 3

2
-1 0

0 -1

3
0 0 0

3 1

출처: Devin.KR 자체 제작