Counting Even Product Subarrays

Given an array of integers, your task is to count the number of contiguous subarrays such that their product is even.

A product is even if and only if at least one number in the subarray is even. In mathematical terms, a subarray’s product is even if (\exists; i) such that (a_i) is even.

You need to read the input from standard input (stdin) and print the output to standard output (stdout).

inputFormat

The first line contains a single integer (n) (the size of the array).

The second line contains (n) integers separated by spaces representing the elements of the array.

outputFormat

Output a single integer — the number of contiguous subarrays whose product is even.## sample

4
1 2 3 4

8