Count Odd Sum Pairs

You are given an array of integers. Your task is to count the number of pairs of indices (i, j) such that 0 ≤ i < j < n (where n is the number of elements in the array) and the sum of the corresponding elements is an odd number.

A sum of two integers is odd if and only if one of them is even and the other is odd.

For example, given the array [1, 2, 3, 4], the valid pairs are:

• (1, 2) because 1 + 2 = 3 (odd)
• (1, 4) because 1 + 4 = 5 (odd)
• (3, 2) because 3 + 2 = 5 (odd)
• (3, 4) because 3 + 4 = 7 (odd)

Thus, the answer is 4.

Input/Output Format: The input is read from standard input (stdin) and the output is written to standard output (stdout).

inputFormat

The first line of input contains a single integer n which represents 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 pairs (i, j) where 0 ≤ i < j < n and the sum of the two corresponding elements is odd.

## sample

4
1 2 3 4

4