题目来源：http://codeforces.com/contest/1118/problem/B

B. Tanya and Candies

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Tanya has nn candies numbered 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

Copy

7
5 5 4 5 5 5 6

output

Copy

2

input

Copy

8
4 8 8 7 8 4 4 5

output

Copy

2

input

Copy

9
2 3 4 2 2 3 2 2 4

output

Copy

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].

思路：奇偶前缀和

参考代码：

#include<iostream>
#define ll long long int
using namespace std;
#define N 200005
ll ans[N],jj[N],oo[N];
int main()
{
    cin.sync_with_stdio(false);
    ll q;
    cin>>q;
    for(int i=1; i<=q; i++)
        cin>>ans[i];
    jj[1]=ans[1];
    oo[1]=0;
    for(int i=2; i<=q; i++)
    {
        if(i&1)
        {
            jj[i]=ans[i]+jj[i-1];
            oo[i]=oo[i-1];
        }
        else
        {
            jj[i]=jj[i-1];
            oo[i]=oo[i-1]+ans[i];
        }
    }
    int sum=0;
    for(int i=1; i<=q; i++)
        {
            if(jj[i-1]+oo[q]-oo[i]==oo[i-1]+jj[q]-jj[i])
                sum++;
        }
        cout<<sum<<endl;
    return 0;
}