Cho số nguyên dương ~n~ và dãy số nguyên không âm gồm ~n~ phần tử ~a_1, a_2, ..., a_n~. Hãy cho biết có bao nhiêu cách chọn cặp chỉ số ~(i, j)~, trong đó ~(1 ≤ i, j ≤ n; i ≠ j)~ sao cho sau khi xoá 2 phần tử ~a_i, a_j~ khỏi dãy thì tổng giá trị các phần tử còn lại trong dãy là số chẵn. Hai cặp chỉ số được chọn ~(i, j)~ và ~(j, i)~ được tính là 1 cách chọn; hai cách chọn được coi là khác nhau nếu tồn tại ít nhất một chỉ số khác nhau.

Input

Dòng 1 chứa số nguyên dương ~n~ (~2 ≤ n ≤ 10^6~).

Dòng 2 chứa ~n~ số nguyên là giá trị của các phần tử ~a_1, a_2, ..., a_n~ (~0 ≤ a_i ≤ 10^9~).

Output

Một số nguyên duy nhất là kết quả bài toán.

Sample Test

Input

5
1 6 3 8 4

Output

4

Giải thích

Có ~4~ cách chọn cặp chỉ số (~i, j~): Cách 1 chọn cặp (~i = 1, j = 3~) tổng còn lại: ~a_2 + a_4 + a_5 = 6 + 8 + 4 = 18~ là số chẵn. Tương tự có thêm các cách chọn cặp (~i, j~) là: (~2, 4~); (~2, 5~); (~4, 5~).

Ràng buộc:

• Có ~50\%~ số test ứng với ~50\%~ số điểm thỏa mãn: ~n ≤ 10^3~;
• ~50\%~ số test còn lại ứng với ~50\%~ số điểm không có ràng buộc gì thêm.