3SUM は、与えられた整数列 $c_1, c_2, \dots, c_m$ に対して $i < j < k$ かつ $c_i + c_j + c_k = 0$ を満たす3つの添字を見つけるという、よく知られたアルゴリズム問題です。

任意の整数列に対してこの問題を $O(m^2)$ よりも大幅に優れた計算量で解く方法は知られていません。幸いなことに、Bajtek はそのことを知らず、自身の「非常に気に入った数列（Bardzo Ulubiony Ciąg）」に対してこの問題を解くことにしました。

Bajtek の「気に入った数列」は $n$ 個の整数 $a_1, a_2, \dots, a_n$ から構成されます。Bajtek の「非常に気に入った数列」は、元の数列のすべての $\frac{n(n+1)}{2}$ 個の連続する部分区間の和を計算し、それらすべての和を一つの数列に並べることで生成されます（重複も考慮します）。部分区間の和は、区間の開始位置の添字の昇順に並べ、開始位置が同じ場合は終了位置の添字の昇順に並べます。

簡単すぎないように、Bajtek は $i < j < k$ となる添字の組を見つけることには興味がありません。彼は、和が 0 になるような要素に対応する添字の組 $i < j < k$ の総数を知りたがっています。彼のために、そのような組の数を計算するプログラムを作成してください。

入力

標準入力の最初の行には、Bajtek の「気に入った数列」の長さを表す整数 $n$ ($1 \le n \le 500$) が与えられます。

次の行には、Bajtek の「気に入った数列」の各要素を表す $n$ 個の整数 $a_i$ ($|a_i| \le 20\,000$) が与えられます。

出力

標準出力の最初の行に、Bajtek の「非常に気に入った数列」の要素のうち、和が 0 になるような添字の組 $i < j < k$ の数を表す整数を1つ出力してください。

入出力例

入力 1

3
7 -4 -2

出力 1

1

入力 2

10
0 0 0 0 0 0 0 0 0 0

出力 2

26235

注記

最初の例では、Bajtek の「非常に気に入った数列」は $[7, 3, 1, -4, -6, -2]$ となり、和が 0 になる異なる要素の組は $3 + 1 + (-4)$ の1つだけであるため、答えは 1 です。

2番目の例では、Bajtek の「非常に気に入った数列」は 55 個の 0 から構成されます。任意の 3 つの添字 $i < j < k$ について、それらに対応する要素の和は 0 となり、そのような組は 26235 個存在します。