你有数组 a[1], a[2], ..., a[n],由 n 个整数组成。计算将数组的所有元素分成三个连续部分以使每个部分的元素之和相同的方法的数量。
更正式地说,您需要找到这样的索引对 i, j (2 ≤ i ≤ j ≤ n - 1) 的数量,即 $$\sum_{k=1}^{i-1}a_k=\sum_{k=i}^ja_k=\sum_{k=j+1}^na_k$$。
输入
第一行包含整数n (1 ≤ n ≤ 5·105),显示数组中有多少个数字。第二行包含 n 个整数 a[1], a[2], ..., a[n] (|a[i]| ≤ 109) — 数组 a 的元素。
输出
打印一个整数 — 将数组分成具有相同总和的三个部分的方法数。
示例
输入 #1
5 1 2 3 0 3
输出 #1
2
输入 #2
4 0 1 -1 0
输出 #2
1
输入 #3
2 4 1
输出 #3
0