Even Sum Subarrays

You are given an integer n and a list of n integers. Your task is to determine the number of contiguous subarrays whose sum is even.

Let \(A = [a_1, a_2, \dots, a_n]\) be the array of integers. A subarray is defined by the indices \(i\) and \(j\) with \(1 \le i \le j \le n\). The subarray \(A[i \dots j]\) has an even sum if \[ \sum_{k=i}^{j} a_k \equiv 0 \pmod{2}. \]

Consider the prefix sums of the array. An important observation is that a subarray from index i to j has an even sum if the parity of the prefix sum up to i-1 is the same as that up to j. Use this result to compute the answer efficiently.

inputFormat

The input is read from standard input (stdin) and formatted as follows:

• The first line contains a single integer n which denotes the size of the array.
• The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output a single integer representing the number of contiguous subarrays whose sum is even. The output should be printed on standard output (stdout).

## sample

5
1 2 3 4 5

6

</p>