Even Sum Pairs

Given an array A of size N, find the number of pairs of indices \( (i, j) \) such that \( i < j \) and the sum \( A[i] + A[j] \) is even.

In other words, you need to count the number of pairs that satisfy the condition \( A[i] + A[j] \equiv 0 \pmod{2} \). A straightforward approach is to count the number of even and odd numbers in the array and then calculate the number of valid pairs using the combinatorial formula: \( \binom{k}{2} = \frac{k \times (k - 1)}{2} \), where k is the count of numbers (either even or odd).

Your task is to implement an efficient solution that reads input from stdin and writes the output to stdout.

inputFormat

The first line contains a single integer N, the number of elements in the array.

The second line contains N space-separated integers representing the array A.

outputFormat

Output a single integer representing the number of pairs \( (i, j) \) (with \( i < j \)) such that the sum \( A[i] + A[j] \) is even.

4
1 2 3 4

2