Our friend Monk was given an integer array A of size N. He got a task to calculate the Absolute Difference between the number of odd and even pairs present in this array A.

A Pair of 2 integers $(i,j)$ is called an odd pair, if $i < j$, and $A[i]+A[j]$ is not divisible by 2. A pair of integers $(i,j)$ is called even, if $i < j$, and $A[i]+A[j]$ is divisible by 2.

This task seems a little bit tricky to him, and wants you to help him out. Can you ?

Input Format:

The first Line contains an integer N denoting the size of array. The next line contains N space separated integers, where the $i^{th}$ integer denotes $A[i]$.

Output Format :

Print the required answer on a single line.

Constraints:

$1 \le N \le 100000$

$1 \le A[i] \le 100000$