You are given a list of n positive integers a_1, a_2 ... a_n.

Output the number of unique pairs of integers in the list such that that they add to an even number.

NOTE: Two pairs are unique to each other if and only if at least one of the indices of the numbers of the first pair is different to the second pair.

Input

Your first line will contain a single integer n.

Your second line will contain n space-separated integers representing a_1, a_2 ... a_n.

2 ≤ n ≤ 100,000

Output

Your first and only line of output should contain a single integer representing the number of unique pairs of integers with an even sum.

Example

Input 1
3
1 1 1

Output 1
3

Input 2
6
2 12 3 14 29 4

Output 2
7