Problem Description

Translated from PA 2024 Round 5 Bardzo Ulubiony Ciąg, thanks to Macaronlin for the translation

Given an integer array \( a \) of length \( n \), all subinterval sums of \( a \) form an array \( b \) of length \( \frac{n(n+1)}{2} \). The subinterval sums are arranged in increasing order of the starting index of the intervals. If the starting indices are the same, they are arranged in increasing order of the ending indices.

For the newly formed array \( b \), find the number of tuples \( (i, j, k) \) such that \( b_i + b_j + b_k = 0 \) with \( i < j < k \).

Input Format

The first line contains an integer \( n \) (\( 1 \le n \le 500 \)), representing the length of array \( a \).

The second line contains \( n \) integers \( a_1, a_2, \ldots, a_n \) (\( |a_i| \le 20,000 \)), representing the array \( a \).

Output Format

Output a single integer, which is the number of tuples \( (i, j, k) \) in array \( b \) that satisfy \( b_i + b_j + b_k = 0 \) with \( i < j < k \).

Sample Input and Output

Sample Input #1

3
7 -4 -2

Sample Output #1

1

Sample Input #2

10
0 0 0 0 0 0 0 0 0 0

Sample Output #2

26235

Notes

Sample Explanation 1

The array \( b \) is \([7, 3, 1, -4, -6, -2]\). Only the elements \( 3, 1, -4 \) satisfy the condition, so the answer is \( 1 \).

Sample Explanation 2

The array \( b \) consists of 55 zeros. Any three indices \( i < j < k \) satisfy the sum being zero, hence the answer is \( 26235 \).

见题面 Input 部分

见题面 Output 部分