题目描述

一个数组 $\{a_1, a_2, \cdots, a_m\}$ 被称为妙妙数组，当且仅当其中有一个数（存在一个数）等于其他数相加的结果。也就是，存在一个 $a_x$ ，满足 $a_x = a_1 + a_2 + \cdots + a_{x-1} + a_{x+1} + a_{x + 2} + \cdots + a_m$ 。比如，数组 [1, 3, 2] 是一个妙妙数组，因为 3 = 1 + 2 。数组 [2, 2, 2, 6] 是一个妙妙数组，因为 6 = 2 + 2 + 2。而数组 [1, 2, 4] 不是一个妙妙数组，因为没有一个数等于其他两个数的和。

一个长度为 $n$ 数组有 $n$ 个前缀，第 $i$ 个前缀为其前 $i$ 个数构成的数组。例如，数组 [1, 1, 2, 4] 的前缀有 4 个，分别为 [1], [1, 1], [1, 1, 2], [1, 1, 2, 4] 。

现在给你一个长度为 $n$ 的数组 $\{a_1, a_2, \cdots, a_n \}$ ，求它的所有 $n$ 个前缀中，有几个前缀是妙妙数组。例如，在 [1, 1, 2, 4] 的前缀中，[1, 1],[1, 1, 2] 和 [1, 1, 2, 4] 都是妙妙数组，所以共有 3 个妙妙数组。

输入输出格式

输入格式

输入共两行。

第 $1$ 行包含一个正整数 $n$ ，表示数组的长度。

第 $2$ 行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$ ，表示这个数组。

输出格式

一行共 $1$ 个正整数，代表输入数组的前缀中妙妙数组的个数。

样例

4
1 1 2 4

3

数据范围

对于30%的数据，有 $n \leq 10$ 。

对于50%的数据，有 $n \leq 1000$ 。

对于100%的数据，有 $n \leq 10^5, 0 \leq a_i \leq 10^{13}$ 。