Even Sum Subarrays

Given an array of integers, determine the number of contiguous subarrays whose sum is even. A subarray is a contiguous sequence of elements within the array. The sum of a subarray is even if it is divisible by 2, i.e. (\text{sum} \mod 2 = 0).

For example, given the array [1, 2, 3, 4], there are 4 subarrays with an even sum.

inputFormat

The first line contains a single integer (n) representing the number of elements in the array. The second line contains (n) space-separated integers denoting the elements of the array.

outputFormat

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

4
1 2 3 4

4