题目描述

给出一个长度为 $n$ 的序列 $a$，问有多少种方案将序列 $a$ 划分为恰好连续的三段（每个元素都属于某一段），使得每一段的和都相等。

输入格式

第一行一个整数 $n$，表示序列长度，$1\le n\le 10^5$。

第二行 $n$ 个整数用空格隔开，第 $i$ 个整数表示 $a_i$。

输出格式

一行一个整数表示方案数。

4
1 2 3 3

1

5
1 2 3 4 5

0