Problem K
Kinda Ok Array Problem
This is an array problem.
You are given an array $A$ that contains $N$ numbers, $A_1, \dots , A_ N$. Count the number of distinct subarrays of $A$ where the sum of the elements in the subarray is even.
Note that an subarray is a contiguous part of an array (E.g. $[2, 3, 4]$ is a subaarray of $[1, 2, 3, 4, 5]$). Two subarrays $B_ i$ and $C_ i$ are considered identical if they are of the same length $k$ and for $1 \leq i \leq k, B_ i = C_ i$.
Constraints
$1 \leq N \leq
10^6$
$-10^9 \leq A_ i \leq
10^9$
Input
The first line contains a single integer, $N$, the length of both arrays.
The second line contains $N$ space-separated integers,
$A_1, A_2, \dots , A_
N$.
Output
Output a single integer, the number of distinct even sum subarrays.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 8 8 8 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 5 5 4 4 |
5 |
