보급 상자의 같은 재고

문제

마라톤 대회의 한 보급소에서는 물병을 한 개씩 넣거나 꺼내는 작은 상자의 재고를 기록한다. 담당자는 관찰을 시작한 순간과 이후 매분 작업이 끝난 순간에 상자 안의 물병 수를 확인한다. 관찰 시간은 모두 N분이며, 관찰을 시작할 때 상자에는 정확히 N개의 물병이 들어 있다. 상자의 크기는 충분히 커서 관찰 중 물병을 더 넣지 못하는 일은 없다. 각 분에는 물병 한 개를 넣거나, 물병 한 개를 꺼내거나, 아무 작업도 하지 않는다. 이 세 작업은 각각 정수 1, -1, 0으로 기록된다. 한 분에 작업은 최대 한 번만 이루어지며, 해당 분의 기록은 그 분의 작업이 모두 끝난 뒤 재고에 반영된다. 처음에 N개의 물병이 있으므로 주어진 N개의 기록을 처리하는 동안 재고가 음수가 되는 일은 없다. 담당자는 재고가 같은 두 시점을 골라 그 사이의 보급 흐름을 살펴보려고 한다. 관찰 시작 순간을 시점 0, i번째 분의 작업이 끝난 순간을 시점 i라고 한다. 정수 시점 a와 b가 0 ≤ a < b ≤ N을 만족하고 두 시점의 재고가 같으면, 순서쌍 (a, b)를 하나의 조사 대상으로 센다. 이는 a+1번째 분부터 b번째 분까지 넣은 물병 수와 꺼낸 물병 수가 같다는 뜻이다. 서로 다른 순서쌍은 각각 따로 센다. 두 조사 대상의 시간 구간이 겹쳐도 모두 포함하며, 아무 작업도 하지 않은 한 분만으로 이루어진 구간도 조건을 만족하면 포함한다. 관찰 시작 순간 역시 다른 시점과 짝을 이룰 수 있지만, 같은 시점을 두 번 고르는 것은 허용하지 않는다. 작업 기록을 바탕으로 조사 대상의 총개수를 구해야 한다. 조건을 만족하는 순서쌍이 하나도 없으면 총개수는 0이다.

입력

첫째 줄에 관찰 시간 N이 주어진다. N은 1 이상 100,000 이하의 정수다.
둘째 줄에 각 분의 작업 기록을 나타내는 N개의 정수가 시간순으로 공백으로 구분되어 주어진다. 각 정수는 -1, 0, 1 중 하나다.

출력

재고가 같은 두 시점의 순서쌍 개수를 정수 하나로 출력한다. 답은 32비트 부호 있는 정수 범위를 넘을 수 있다.

5
1 -1 0 1 -1

7

3
-1 -1 1

1

2
1 1

0

출처: Devin.KR 자체 제작