Codeforces•Sep 14, 2025

Tanya and Candies

Hazrat Ali

Codeforces

She plans to eat exactly n−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 i (let's call these candies good) that if dad gets the i-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=4 and weights are [1,4,3,3]. Consider all possible cases to give a candy to dad:

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

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

Input

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

The second line of the input contains n integers a1,a2,…,an (1≤ai≤104), where ai is the weight of the i-th candy.

Output

Print one integer — the number of such candies i (good candies) that if dad gets the i-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

Solution
#include <bits/stdc++.h>
using namespace std;

int main()
{

    int n;
    cin >> n;
    vector<int> a(n);
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    int e = 0, o = 0;
    for (int i = 0; i < n; i++)
    {
        if (i % 2 == 0)
        {
            e += a[i];
        }
        else
        {
            o += a[i];
        }
    }
    int ne = 0, no = 0;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        if (i % 2 == 0)
        {
            ans += (ne + o - no) * 2 == sum - a[i];
            ne += a[i];
        }
        else
        {
            ans += (no + e - ne) * 2 == sum - a[i];
            no += a[i];
        }
    }
    cout << ans << endl;
    return 0;
}





Comments