농장 물탱크의 제자리 구간

문제

한 농장은 물탱크로 들어오거나 물탱크에서 나간 물의 양을 작업 기록으로 남긴다. 하루 동안의 기록은 발생한 순서대로 나열되어 있으며, 기록 하나에는 물의 순변화량이 정수로 적혀 있다. 양수는 그만큼 물이 들어왔다는 뜻이고, 음수는 그 절댓값만큼 물이 나갔다는 뜻이다. 값이 0인 기록은 장치를 점검했지만 물의 양은 바뀌지 않았다는 뜻이다. 농장 관리자는 연속한 작업을 묶어 살펴보면서 물탱크의 양이 작업 전과 작업 후에 같아지는 구간을 찾으려 한다. 기록 번호가 l부터 r까지인 구간은 l번 작업 직전부터 r번 작업 직후까지를 의미한다. 이 구간에서 물의 양이 원래대로 돌아왔다는 것은 l번부터 r번까지의 순변화량 합이 정확히 0이라는 뜻이다. 구간 중간에 물의 양이 달라지는 것은 상관없다. 이번 분석에서는 실제 물탱크의 용량이나 처음 들어 있던 물의 양은 고려하지 않는다. 기록은 이미 확인된 자료이며, 주어진 변화량의 합만으로 구간을 판정한다. 기록을 재배열하거나 일부 기록을 건너뛰어서 구간을 만들 수 없다. 또한 작업을 하나도 포함하지 않는 빈 구간은 세지 않는다. 값이 0인 기록 하나만으로 이루어진 구간은 조건을 만족한다. 조건을 만족하는 구간은 서로 겹쳐도 각각 센다. 시작 번호나 끝 번호 중 하나라도 다르면 서로 다른 구간이다. 예를 들어 세 기록의 값이 차례로 2, -2, 0이면 첫 두 기록의 구간, 마지막 기록 하나의 구간, 세 기록 전체의 구간을 각각 센다. 길이가 같거나 같은 변화량이 반복되는 구간도 번호가 다르면 별개다. 전체 기록에서 조건을 만족하는 구간의 개수를 출력한다. 기록이 많으면 정답이 큰 정수가 될 수 있으며, 조건을 만족하는 구간이 하나도 없을 수도 있다.

입력

첫째 줄에 작업 기록 수인 정수 N이 주어진다. 1 ≤ N ≤ 100,000이다.
둘째 줄에 발생 순서대로 정수 A₁, A₂, …, Aₙ이 공백으로 구분되어 주어진다. 모든 i에 대해 -9 ≤ Aᵢ ≤ 9이다.

출력

순변화량의 합이 0인 비어 있지 않은 연속 구간의 개수를 정수로 출력한다. 조건을 만족하는 구간이 없으면 0을 출력한다. 정답은 최대 5,000,050,000이다.

5
2 -2 0 3 -3

6

4
1 2 3 4

0

4
0 0 0 0

10

출처: Devin.KR 자체 제작