У вас есть массив $a$ из $n$ целых чисел. Вам нужно найти количество пар индексов $(i, j)$ таких, что $1 \le i < j \le n$ и сумма $a_i + a_j$ является четным числом.

Входные данные

Первая строка содержит целое число $n$ ($1 \le n \le 10^5$) — количество элементов в массиве.

Вторая строка содержит $n$ целых чисел $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).

Выходные данные

Выведите одно целое число — количество пар $(i, j)$, удовлетворяющих условию.

Примеры

Входные данные 1

4
1 2 3 4

Выходные данные 1

2

Примечание

В первом примере подходящими парами являются $(1, 3)$ (так как $1+3=4$) и $(2, 4)$ (так как $2+4=6$).