问题描述

给定一个长度为 $n$ 的整数数组 $a[1],a[2],\dots,a[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$，表示数组长度。
• 第二行包含 $n$ 个整数 $a[1],a[2],\dots,a[n]$。

输出格式

输出一个整数，表示将数组拆分成三段且三段和相等的方案总数。

样例输入1

5
1 2 3 0 3

样例输出1

2

样例输入2

4
0 1 -1 0

样例输出2

1

样例输入3

2
4 1

样例输出3

0

说明

子任务	占比	$n$	$|a_i|$
$1,2$	$20\%$	$\le 10$	$\le 10^{10}$
$3,4$	$20\%$	$\leq 100$
$5,6,7$	$30\%$	$\le 10^3$
$8,9,10$	$30\%$	$\le 2 \times 10^5$

对全部的测试数据，保证 $1 \le n \le 2 \times 10^5， -10^{10}\le a_i \le 10^{10}$。