# 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 |