K. Kinda Ok Array Problem
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

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.

Scoring

$$$1 \leq N \leq 10^6$$$

$$$-10^9 \leq A_i \leq 10^9$$$

Examples
Input
3
8 8 8
Output
3
Input
4
5 5 4 4
Output
5