Cho 1 dãy số gồm ~N~ phần tử. Hãy cho biết có bao nhiêu cách lựa chọn cặp chỉ số (~i,j~) trong đó (~1 \le i,j \le n,i<>j~) sao cho sau khi xóa 2 phần tử ai,aj khỏi dãy thì tổng các phần tử còn lại trong dãy là số chẵn. Hai cặp chỉ số (~i,j~) và (~j,i~) được tính là một 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.

Dữ liệu vào:

Dòng 1 chứa số nguyên dương ~N~ (~2 \le N \le 10^4~) Dòng 2 chứa n số nguyên là giá trị các phần tử ~a_1, a_2, a_3,... a_n~;(~0 \le a_i\le 10^5~)

Dữ liêu ra:

• Ghi số nguyên ~K~ là kết quả bài toán.

Ví dụ:

Input

5
1 6 3 8 4

Output

4