Triplets Sum Zero in Subarray Sums

You are given an integer array \(a\) of length \(n\). Consider all subarrays of \(a\) and form a new array \(b\) containing the sums of these subarrays. The array \(b\) has length \(\frac{n(n+1)}{2}\) and the subarray sums are listed in the order of increasing starting index; for the same starting index they are listed in order of increasing ending index.

Your task is to find the number of triples \((i, j, k)\) such that \(i < j < k\) and \[ b_i + b_j + b_k = 0 \] where \(b_i, b_j, b_k\) are the elements of \(b\). All formulas must be interpreted in \(\LaTeX\) format.

Note: The input size will be small enough so that a brute-force solution is acceptable.

inputFormat

The first line contains a single integer \(n\) (the length of the array \(a\)). The second line contains \(n\) integers representing the array \(a\). Input elements are separated by spaces.

outputFormat

Output a single integer, which is the number of triplets \((i, j, k)\) (with \(i < j < k\)) such that \(b_i + b_j + b_k = 0\).

sample

3
-1 0 1

8