Odd Sum Pairs

You are given a sequence of n integers. Your task is to count the number of pairs (i, j) (with 1 ≤ i < j ≤ n) such that the sum of the i-th and j-th integer is odd.

The key observation is that the sum of two integers is odd if and only if one of them is odd and the other is even. Therefore, if we let O be the number of odd numbers and E the number of even numbers in the sequence, the answer is given by the formula:

\( \text{Answer} = O \times E \)

Read the input from standard input and output the result to standard output.

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10⁵), representing the number of integers.

The second line contains n space-separated integers. Each integer is between \(-10^9\) and \(10^9\).

outputFormat

Output a single integer — the number of pairs (i, j) such that 1 ≤ i < j ≤ n and the sum of the i-th and j-th integer is odd.

## sample

5
1 3 2 4 5

6

</p>