Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

By Riaz_BSMRSTU · Limits 1s, 512 MB

Mr. Hikiko will react with a “Not Bad”, if you can solve this problem.

An array is a Not Bad array if the sum of all of its element is equal to its length. For example, this array $[1, -1, 3]$ is a Not Bad array since the sum of all its element is $3$ (which is equal to its length).

Given an array. Find the number of non-empty Not Bad sub-arrays of this array.

A sub-array is a contiguous part of an array. For example, consider the array $[1, 2, 3]$. There are 6 non-empty sub-arrays. The sub-arrays are $[1]$, $[2]$, $[3]$, $[1, 2]$, $[2, 3]$, $[1, 2, 3]$.

Input

The first line will contain $N$ ($1 \le N \le 10^6$), the length of the array.

The next line will contain the elements of the array ($-10^9 \le \texttt{each element} \le 10^9$).

Output

Print the number of non-empty Not Bad sub-arrays of given array.

Sample

InputOutput
5
1 -1 3 -1 2

4


Statistics

68% Solution Ratio

skmonirEarliest, May '20

agtxdyFastest, 0.1s

agtxdyLightest, 8.1 MB

Ashraful_jnuShortest, 265B