题目描述

给定长度为 $n$ 的序列 $a$ 。我们定义 $b$ 是一个长度为 $\frac{n(n+1)}{2}$ 的序列，满足 $b_{i+\frac{j(j-1)}{2}}=a_i+a_{i+1}+\dots+a_j$ 。

现在你希望求出有多少对不同的整数 $i,j,k$ ，使得：

1. $1\le i<j<k\le \frac{n(n+1)}{2}$ 。

2. $b_i+b_j+b_k=0$ 。

输入格式

第一行一个整数 $n$ ，表示序列 $a$ 的长度。

第二行包含 $n$ 个整数，第 $i$ 个整数表示 $a_i$ 。

输出格式

输出一行一个整数，表示你求出的答案。

样例

样例输入1

3
7 -4 -2

样例输出1

1

数据范围

对于所有数据，$1\le n\le 500,|a_i|\le 20000$ 。

子任务 1 ( 30% ) : $1\le n\le 20$ 。

子任务 2 ( 30% ) : $1\le n\le 100$ 。

子任务 3 ( 40% ) : 无特殊限制。