Even Product Pairs

Given a list of N integers, your task is to find the number of pairs of indices \((i, j)\) such that:

• \(1 \leq i < j \leq N\)
• The product \(a_i \times a_j\) is even.

A product of two numbers is even if at least one of the factors is even. In other words, you need to count all pairs in which at least one number is even.

Input/Output is via standard input and standard output. See the Input and Output sections for detailed format.

inputFormat

The first line contains a single integer \(N\), the number of elements in the list. The second line contains \(N\) space-separated integers representing the list \(a_1, a_2, \dots, a_N\).

outputFormat

Output a single integer representing the number of pairs \((i, j)\) with \(1 \leq i < j \leq N\) such that the product \(a_i \times a_j\) is even.

## sample

4
3 4 1 2

5

</p>