Even Sum Pairs

You are given an integer n and an array of n integers. Your task is to count the number of pairs \((i,j)\) such that \(1 \leq i < j \leq n\) and the sum \(a_i + a_j\) is even.

Recall that the sum of two integers is even if both integers are even or both are odd. In mathematical terms, if we denote by \(E\) the number of even numbers and by \(O\) the number of odd numbers in the array, the number of valid pairs is given by:

\[ \text{even pairs} = \binom{E}{2} \quad \text{and} \quad \text{odd pairs} = \binom{O}{2}, \]

and the answer is the sum of these two quantities.

inputFormat

The first line of input contains an integer n representing the number of elements in the array. The second line contains n integers separated by spaces.

outputFormat

Output a single integer representing the number of pairs \((i,j)\) such that \(1 \leq i < j \leq n\) and \(a_i + a_j\) is even.

5
1 2 3 4 5

4