3SUM is a well-known algorithmic problem where, for a given sequence of integers $c_1, c_2, \dots, c_m$, one must find three indices $i < j < k$ such that $c_i + c_j + c_k = 0$.

There is no known solution to this problem for arbitrary sequences of integers with complexity significantly better than $O(m^2)$. Fortunately, Bajtek does not know this and has decided to solve this problem for his Very Favorite Sequence.

Bajtek's Favorite Sequence consists of $n$ integers $a_1, a_2, \dots, a_n$. Bajtek's Very Favorite Sequence is formed by looking at all $\frac{n(n+1)}{2}$ contiguous subsegments of Bajtek's Favorite Sequence, calculating the sum of elements in each, and placing all these sums into a single sequence (including repetitions). The subsegment sums are ordered by the starting index of the subsegment, and in case of a tie, by the ending index of the subsegment.

To make things not too simple, Bajtek is not interested in finding a triple of indices $i < j < k$. He would like to know the exact number of all triples of indices $i < j < k$ corresponding to elements that sum to zero. Help him and write a program that calculates the number of such triples for him!

Input

The first line of standard input contains an integer $n$ ($1 \le n \le 500$), representing the length of Bajtek's Favorite Sequence.

The next line contains $n$ integers $a_i$ ($|a_i| \le 20\,000$), representing the consecutive elements of Bajtek's Favorite Sequence.

Output

The first and only line of standard output should contain a single integer — the number of triples of indices $i < j < k$ corresponding to elements of the Very Favorite Sequence that sum to 0.

Examples

Input 1

3
7 -4 -2

Output 1

1

Input 2

10
0 0 0 0 0 0 0 0 0 0

Output 2

26235

Note

In the first example test, the Very Favorite Sequence is $[7, 3, 1, -4, -6, -2]$, and the only triple of distinct elements summing to 0 is $3 + 1 + (-4)$, hence the answer is 1.

In the second example test, Bajtek's Very Favorite Sequence consists of fifty-five zeros. For any three indices $i < j < k$, the sum of the corresponding elements is equal to 0, and there are 26,235 such triples.