Count Even Sum Subarrays

Given an array of integers, your task is to compute the number of contiguous subarrays whose sum is even.

A subarray is a contiguous segment of the array. More formally, for an array \(a_1, a_2, \ldots, a_n\), count the number of pairs \((i, j)\) with \(1 \le i \le j \le n\) such that the sum \(S = \sum_{k=i}^{j} a_k\) is even.

Note that the array elements can be negative, zero, or positive.

inputFormat

The first line contains an integer (n) ((1 \le n \le 1000)), representing the number of elements in the array. The second line contains (n) space-separated integers, representing the elements of the array.

outputFormat

Output a single integer: the number of contiguous subarrays with an even sum.## sample

1
1

0