给定一个长度为 n 的数组 a1,a2,…,an。

现在，要将该数组从中间截断，得到三个非空子数组。

要求，三个子数组内各元素之和都相等。

请问，共有多少种不同的截断方法？

输入格式

第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,an。

输出格式

输出一个整数，表示截断方法数量。

数据范围

前六个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤10^5，−10000≤ai≤10000。

输入样例1：

1
2
4
1 2 3 3

输出样例1：

1
1

输入样例2：

1
2
5
1 2 3 4 5

输出样例2：

1
0

输入样例3：

1
2
2
0 0

输出样例3：

1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;

int n;
int s[N];

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &x);
		s[i] = s[i - 1] + x;
	}

	if (s[n] % 3)
		puts("0");
	else {
		LL res = 0, cnt = 0;
		for (int j = 2; j < n; j++) {
			if (s[j - 1] == s[n] / 3) cnt++;
			if (s[j] == s[n] / 3 * 2) res += cnt;
		}

		printf("%lld\n", res);
	}

	return 0;
}