题目描述

我们称一个数组 $a$ 是 平衡 的，当且仅当：

• 1、可以将 $a$ 划分成 $2$ 个非空的 子数组 $x$ 和 $y$
• 2、子数组 $x$ 和 $y$ 的和相等

比如：

• $a = [1, 3, 2]$ 是平衡的，因为 $a$ 可以划分成 $x = [1, 2]$ 和 $y = [3]$，而 $x$ 和 $y$ 的和都是 $3$
• $a = [1, 2, 4]$ 不是平衡的

现在给你一个长度为 $n$ 的数组 $a$，请问 $a$ 有多少个子数组是平衡的呢？

输入格式

第一行一个整数 $n$，表示数组 $a$ 的大小。

第 $2$ 至 $n+1$ 行，每行一个数 $a_i$，表示数组 $a$ 里的数。

输出格式

输出一个数表示平衡的子数组个数。

4 
1 
2 
3 
4 

3 

3
1
1
1

3

数据范围与提示

【样例 1 解释】

共存在 $3$ 个不同的平衡子数组:

• $[1,2,3]$ 可以划分为 $[1,2]$ 与 $[3]$
• $[1,3,4]$ 可以划分为 $[1,3]$ 与 $[4]$
• $[1,2,3,4]$ 可以划分为 $[1,4]$ 与 $[2,3]$

【样例 2 解释】

共存在 $3$ 个不同的平衡子数组（标记橙色部分）:

• $[{\color{orange}{\bf 1}}, {\color{orange}{\bf 1}}, 1]$
• $[{\color{orange}{\bf 1}}, 1, {\color{orange}{\bf 1}}]$
• $[1, {\color{orange}{\bf 1}}, {\color{orange}{\bf 1}}]$
• 注意：两个子数组不同，当且仅当存在至少一个下标不同

【数据范围】

• $1\le n\le 20$，$1\le a_i\le 10^8$。