题目描述

给定数组 $a[1],a[2],\dots,a[n]$，数组包含 $n$ 个整数。请统计将数组全部元素分割为三段连续子数组的方案数，要求分割得到的每一段元素的总和相等。

更正式地讲，你需要统计满足条件的下标对 $i,j$（$2 \le i \le j \le n-1$）的数量，使得：

$$\sum_{k=1}^{i-1} a_k=\sum_{k=i}^{j} a_k=\sum_{k=j+1}^{n} a_k$$

输入

第一行输入一个整数 $n$（$1 \le n \le 5\cdot 10^5$），代表数组元素的个数。

第二行输入 $n$ 个整数 $a[1],a[2],\dots,a[n]$（$|a[i]| \le 10^9$），为数组的各个元素。

输出

输出单个整数，代表把数组分割为三段且每段总和相等的分割方案总数。

样例

5
1 2 3 0 3

2

4
0 1 -1 0

1

2
4 1

0

原题链接

原题链接