题目描述

你得到了一个数组 $a$，包含 $n$ 个数字。

现在你要找到把它分成三份的方法，使得每一份之内所有数的和相等。

简单地说，你需要找到一个数对 $(i,j)$，使得 $\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 500000)$，表示数列中有多少个数。

接下来一行有 $n$ 个数 $a_i$，$|a_i|\le 10^9$。

输出格式

一行一个整数，表示满足条件的 $(i,j)$ 的总数。

5
1 2 3 0 3

2

4
0 1 -1 0

1

2
4 1

0