【題解】Tanya and Candies 

Tanya has nn candies numTanya and Candies bered from 11 to nn. The ii-th candy has the weight aiai.

She plans to eat exactly n−1n−1 candies and give the remaining candy to her dad. Tanya eats candies in order of increasing their numbers, exactly one candy per day.

Your task is to find the number of such candies ii (let's call these candies good) that if dad gets the ii-th candy then the sum of weights of candies Tanya eats in even days will be equal to the sum of weights of candies Tanya eats in odd days. Note that at first, she will give the candy, after it she will eat the remaining candies one by one.

For example, n=4n=4 and weights are [1,4,3,3][1,4,3,3]. Consider all possible cases to give a candy to dad:

• Tanya gives the 11-st candy to dad (a1=1a1=1), the remaining candies are [4,3,3][4,3,3]. She will eat a2=4a2=4 in the first day, a3=3a3=3 in the second day, a4=3a4=3 in the third day. So in odd days she will eat 4+3=74+3=7 and in even days she will eat 33. Since 7≠37≠3 this case shouldn't be counted to the answer (this candy isn't good).
• Tanya gives the 22-nd candy to dad (a2=4a2=4), the remaining candies are [1,3,3][1,3,3]. She will eat a1=1a1=1 in the first day, a3=3a3=3 in the second day, a4=3a4=3 in the third day. So in odd days she will eat 1+3=41+3=4 and in even days she will eat 33. Since 4≠34≠3 this case shouldn't be counted to the answer (this candy isn't good).
• Tanya gives the 33-rd candy to dad (a3=3a3=3), the remaining candies are [1,4,3][1,4,3]. She will eat a1=1a1=1 in the first day, a2=4a2=4 in the second day, a4=3a4=3 in the third day. So in odd days she will eat 1+3=41+3=4 and in even days she will eat 44. Since 4=44=4 this case should be counted to the answer (this candy is good).
• Tanya gives the 44-th candy to dad (a4=3a4=3), the remaining candies are [1,4,3][1,4,3]. She will eat a1=1a1=1 in the first day, a2=4a2=4 in the second day, a3=3a3=3 in the third day. So in odd days she will eat 1+3=41+3=4 and in even days she will eat 44. Since 4=44=4 this case should be counted to the answer (this candy is good).

In total there 22 cases which should counted (these candies are good), so the answer is 22.

Input

The first line of the input contains one integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the number of candies.

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1041≤ai≤104), where aiai is the weight of the ii-th candy.

Output

Print one integer — the number of such candies ii (good candies) that if dad gets the ii-th candy then the sum of weights of candies Tanya eats in even days will be equal to the sum of weights of candies Tanya eats in odd days.

Examples

Input

7
5 5 4 5 5 5 6
      

Output

2
      

Input

8
4 8 8 7 8 4 4 5
      

Output

2
      

Input

9
2 3 4 2 2 3 2 2 4
      

Output

3
      

Note

In the first example indices of good candies are [1,2][1,2].

In the second example indices of good candies are [2,3][2,3].

In the third example indices of good candies are [4,5,9][4,5,9].

【題意】要求删去一個數，使得剩下的數中第奇數個數的和與第偶數個的和相同。求可能删去的數情況總數。

【解題思路】類似尺取法，先用sum數組求和（奇數個加，偶數個減的方式），周遊每一個數，看看删除後是否符合題意。根據删去第i個數後sum[i-1] 是否與sum[n]-sum[i]相等來判别。（删除第i個數後，第i個數後的奇偶性發生變化。

【代碼】

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <queue>
#include <vector>
#include <memory.h>
#include <stack>
typedef long long LL;
using namespace std;
const int maxn = 2e5+10;
int n, a,sum[maxn];

int main()
{
    while(scanf("%d",&n)!=EOF )
    {
        sum[0] = 0;
        for(int i = 1; i <= n; i++)
        {
            scanf("%d",&a);
            if(i%2)
                sum[i] = sum[i-1]+a;
            else sum[i] = sum[i-1]-a;
        }
        //cout << sum[n] << endl;
        int ans = 0;
        for(int i = 1; i <= n; i++)
        {
            int k1 = sum[n]-sum[i];
            int k2 = sum[i-1];
            if(k1==k2) ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}