Counting Subarrays with Odd Sum

You are given a positive integer N and an array of N positive integers. Your task is to count the number of subarrays whose sum is odd.

A subarray is a contiguous part of the array. For an array a[1..N], a subarray a[i..j] is defined for any indices 1 \le i \le j \le N.

The key idea is to use prefix sums and count the parity (odd or even) of these sums. Let P[k] be the prefix sum for the first k elements, where P[0] = 0. The sum of a subarray a[i..j] is P[j] - P[i-1] and it is odd if and only if:

[ (P[j] - P[i-1]) \equiv 1 \pmod{2} \quad \Longleftrightarrow \quad P[j] \text{ and } P[i-1] \text{ have opposite parity.} ]

Count the number of pairs of indices for which the prefix sums have opposite parity.

inputFormat

The first line contains an integer N (which can be zero) denoting the number of elements in the array.

The second line contains N space-separated positive integers representing the array elements. If N = 0, the second line will be empty.

outputFormat

Output a single integer representing the number of subarrays with an odd sum.

4
1 2 3 4

6