题目描述

薯条哥是一个游戏爱好者，他喜欢用数字和算法解决各种难题。有一天，他遇到了一个有趣的问题。他手头有一个环形数组 $a$ ，数组中有 $n$ 个数字。

他想玩一个游戏，用两刀把它切割成两段，使得两段的数字之和相等。他可以选择在任何两个数字之间切割，但是他必须确保切割的两段都不为空。

薯条哥非常聪明，很快就意识到这是一个非常有趣的问题。他开始思考如何解决这个问题，并且尝试了很多不同的方法，还是没有想出来如何解决。

于是，薯条哥想分享这个问题并且寻求你的帮助。他想知道有多少种不同的切割方案可以使得两段数字之和相等。

输入描述

第一行输入一个正整数 $n(1\le n\le 10^5)$ ，代表环形数组的元素数量。

第二行输入 $n$ 个正整数 $a_i(-10^9\le a_i\le 10^9)$，代表环形数组的元素。

输出描述

输出一个整数，代表切割的方案数。

样例

输入

5
1 4 -2 5 2

输出

2