Cho dãy ~a~ có ~n~ phần tử: ~a_1, a_2, \ldots, a_n~.

Yêu cầu: Hãy đếm số cặp vị trí ~i~, ~j~ sao cho ~a_i \ge a_j~ và tổ hợp chập ~a_j~ của ~a_i~ chẵn. Hay nói cách khác, bạn hãy đếm số lượng cặp số ~i, j~ sao cho:

• ~1 \le i, j \le n~.

• ~a_i \ge a_j~.

• ~\binom{a_i}{a_j} \equiv 0 \pmod{2}~.

Input

Vào từ file văn bản evencomb.inp:

• Dòng đầu tiên ghi một số nguyên ~n~ là số phần tử của dãy ~a~ (~1 \le n \le 10^6~).

• Dòng thứ hai ghi ~n~ số nguyên mô tả dãy số ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^6~)

Output

Xuất ra file văn bản evencomb.out một số nguyên là số cặp ~i~, ~j~ thỏa mãn yêu cầu đề bài.

Scoring

Sample Input 1

7
4 7 4 2 7 1 1

Sample Output 1

8

Notes

Giải thích ví dụ:

Các cặp số ~(i, j)~ thỏa mãn điều kiện đề bài là:

1. ~(1, 4)~, ~\binom{a_{1}}{a_{4}} = \binom{4}{2} = 6~

2. ~(1, 6)~, ~\binom{a_{1}}{a_{6}} = \binom{4}{1} = 4~

3. ~(1, 7)~, ~\binom{a_{1}}{a_{7}} = \binom{4}{1} = 4~

4. ~(3, 4)~, ~\binom{a_{3}}{a_{4}} = \binom{4}{2} = 6~

5. ~(3, 6)~, ~\binom{a_{3}}{a_{6}} = \binom{4}{1} = 4~

6. ~(3, 7)~, ~\binom{a_{3}}{a_{7}} = \binom{4}{1} = 4~

7. ~(4, 6)~, ~\binom{a_{4}}{a_{6}} = \binom{2}{1} = 2~

8. ~(4, 7)~, ~\binom{a_{4}}{a_{7}} = \binom{2}{1} = 2~