Practice on Toph

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

Not Bad Array

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][1, -1, 3] is a Not Bad array since the sum of all its element is 33 (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][1, 2, 3]. There are 6 non-empty sub-arrays. The sub-arrays are [1][1], [2][2], [3][3], [1,2][1, 2], [2,3][2, 3], [1,2,3][1, 2, 3].

Input

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

The next line will contain the elements of the array (109each element109-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

    Discussion

    Statistics


    68% Solution Ratio

    skmonirEarliest, May '20

    agtxdyFastest, 0.1s

    agtxdyLightest, 8.1 MB

    Ashraful_jnuShortest, 265B

    Submit

    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.