问题 D: 方法的数量
内存限制：256 MB
时间限制：2 S
题面：传统
评测方式：文本比较
上传者：
提交：14
通过：7
题目描述
你有一个数组a[1],a[2],...,a[n]，由n个整数组成。计算有多少种方法可以将数组中的所有元素分成三个连续的部分，使每个部分的元素之和相同。
更正式地说，你需要找到这样的索引对i,j（2≤i≤j≤n-1）的数量，即下图所示。
You've got array a[1],a[2],...,a[n], consisting of n integers. Count the number of ways to split all the elements of the array into three contiguous parts so that the sum of elements in each part is the same.
More formally, you need to find the number of such pairs of indices i,j (2≤i≤j≤n-1), that
.
更正式地说，你需要找到这样的索引对i,j（2≤i≤j≤n-1）的数量，即下图所示。
You've got array a[1],a[2],...,a[n], consisting of n integers. Count the number of ways to split all the elements of the array into three contiguous parts so that the sum of elements in each part is the same.
More formally, you need to find the number of such pairs of indices i,j (2≤i≤j≤n-1), that
.
Input
The first line contains integer n (1≤n≤5·105), showing how many numbers are in the array. The second line contains n integers a[1], a[2], ..., a[n] (|a[i]|≤109) − the elements of array a.
Output
Print a single integer − the number of ways to split the array into three parts with the same sum.
Examples
Input
5 1 2 3 0 3
Output
2
Input
4 0 1 -1 0
Output
1
Input
2 4 1
Output
0
输入格式
第一行包含整数n (1≤n≤5-105)，显示数组中有多少个数字。第二行包含n个整数a[1], a[2], ..., a[n] (|a[i]|≤109) - 数组a的元素。
输出格式
打印一个整数--将数组分成三部分且总和相同的方法的数量。
输入样例 复制
5
1 2 3 0 3输出样例 复制
2