Even Sum Pairs

Given an array of integers, your task is to determine the number of pairs (i, j) such that the sum \(a_i + a_j\) is even. Two numbers sum to an even value if both are even or both are odd. In other words, if there are \(E\) even numbers and \(O\) odd numbers in the array, then the total number of valid pairs is given by \(\binom{E}{2} + \binom{O}{2}\), where \(\binom{n}{2} = \frac{n(n-1)}{2}\).

Your goal is to compute this total number of even-sum pairs.

inputFormat

The first line contains a single integer \(n\) representing 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, which is the number of pairs with an even sum.

5
1 2 3 4 5

4