该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

分段（part）

题目描述

Y 同学有一个长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$。

他想选择两个位置 $i,j$，满足 $1 \le i<j<n$，并把序列分成三段：

• 第一段为 $a_1,\ldots,a_i$；
• 第二段为 $a_{i+1},\ldots,a_j$；
• 第三段为 $a_{j+1},\ldots,a_n$。

请你求出有多少种选择方式，使三段的元素和完全相等。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一行一个整数，表示合法的选择方式数量。

样例

样例输入 #1

5
1 2 3 0 3

样例输出 #1

2

数据范围与约定

对于 $100\%$ 的数据，保证 $3 \le n \le 2\times 10^5$，$-10^9 \le a_i \le 10^9$。

• 特殊性质 A：保证所有 $a_i>0$。
• 特殊性质 B：保证 $\sum_{i=1}^{n}a_i=0$。