题目描述

题目译自 PA 2024 Runda 5 Bardzo Ulubiony Ciąg，感谢 Macaronlin 提供翻译。

给定长度为 $n$ 的整数数组 $a$，$a$ 的所有子区间和形成长度为 $\frac{n(n+1)}{2}$ 的数组 $b$，子区间和按区间开始下标的递增顺序排列，如果区间开始下标相同，则按区间结束递增顺序排列。

对于新形成的数组 $b$，求满足 $b_i + b_j + b_k = 0\ (i < j < k)$ 的 $(i,j,k)$ 对数。

输入格式

第一行一个整数 $n\ (1 \le n \le 500)$，表示数组 $a$ 的长度。

第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n\ (|a_i| \le 20,000)$，表示数组 $a$。

输出格式

一行一个整数，表示数组 $b$ 中满足 $b_i + b_j + b_k = 0\ (i < j < k)$ 的 $(i,j,k)$ 对数。 样例1：

3
7 -4 -2

1

数组 $b$ 为 $[7, 3, 1, -4, -6, -2]$，只有 $3, 1, -4$ 这三个不同元素满足，所以答案为 $1$。

样例2：

10
0 0 0 0 0 0 0 0 0 0

26235

数组 $b$ 为 $55$ 个 $0$，任选三个 $i < j < k$ 都满足和为 $0$，因此答案为 $26,235$。

数据规模与约定

对于 $100\%$ 的数据，$0 \le n \le 10^7$。