Toto học lớp 6 và biết rằng một số nguyên chẵn là chia hết cho 2 còn lẻ là không chia hết cho 2. Ví dụ ~6, -8, 0~ là các số chẵn còn ~45, -27, -13~ là các số lẻ. Toto thích thú với những số chẵn, lẻ như vậy và nhờ bạn giải giúp Toto một bài toán như sau:

Cho dãy số nguyên ~a_1,a_2...a_n~ hãy đếm xem có bao nhiêu bộ ba số có ~a_i, a_j, a_k~ với ~1 \le i < j <k \le n~ mà có tổng chẵn</p>

Input

Dòng đầu chứa số nguyên dương ~n~ có giá trị không vượt quá ~10^5~ là số phần tử của dãy

Dòng cuối chứa n số nguyên có giá trị trong [-32768, 32767]

Ouput

Một số nguyên duy nhất là số bộ có tổng chẵn

Ví dụ

Input

5
-3 2 0 1 2

Output

4

Giải thích: có các bộ có tổng chẵn ~(-3,2,1), (-3,0,1), (-3,1,2) (2,0,2)~