题目背景

PA 2024 5C1

题目描述

题目译自 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)$ 对数。

3
7 -4 -2

1

10
0 0 0 0 0 0 0 0 0 0

26235

提示

样例解释 1

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

样例解释 2

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