Có N chiếc đèn lồng, mỗi chiếc có độ sáng được biểu diễn bằng số nguyên Ai.

Một cặp đèn (i, j) được gọi là "đồng màu" nếu giá trị |Ai - Aj| là số chẵn.

Hãy đếm số lượng cặp "đồng màu".

Input

Dòng 1: số nguyên N (1 ≤ N ≤ 100000).

Dòng 2: N số nguyên Ai (1 ≤ Ai ≤ 10^9).

Output

Số cặp lồng đèn đồng màu