该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

给定一个长度为 $n$ 的整数数组 $a[1],a[2],\dots,a[n]$。请统计将该数组分成三段连续子数组的方案数，使得这三段的元素和都相等。

更形式化地，求满足下标对 $(i,j)$（$2 \le i \le j \le n-1$）的个数，使得

输入格式

• 第一行包含一个整数 $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

说明

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