Cho số nguyên dương n và dãy số nguyên không âm gồm n phần tử a1, a2, a3, ...,an. 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 xóa 2 phần tử ai, aj 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à 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 từ file văn bản ESUM.INP có cấu trúc:

• 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ử a1, a2, a3, ...,an (0 ≤ ai ≤ 10^6).

Kết quả: Ghi vào file văn bản ESUM.OUT một số nguyên là kết quả bài toán.

Ví dụ:

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: a2 + a4 + a5 = 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.