CF466C.Number of Ways

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 .

你有一个由 $ n $ 个整数组成的数组 $ a[1],,a[2],,\dots,,a[n] $。请计算将该数组的所有元素划分为三个连续部分的方法数，使得每一部分的元素之和均相等。

更准确地说，你需要找出满足如下条件的下标对 $ (i,,j) $ 的个数（其中 $ 2 \leq i \leq j \leq n-1 $）：

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.

第一行包含一个整数 $n$（$1 \leq n \leq 5 \cdot 10^5$），表示数组中数字的个数。
第二行包含 $n$ 个整数 $a[1], a[2], \dots, a[n]$（$|a[i]| \leq 10^9$）—— 数组 $a$ 的元素。

Print a single integer — the number of ways to split the array into three parts with the same sum.

输出一个整数——将数组划分为三部分且每部分和相等的方案数。