Cho dãy n số nguyên không âm a_1, a_2,..., a_n. Người ta muốn chọn 2 chỉ số i, j sao cho 1 \leq i \leq j \leq N và xoá khỏi dãy 2 số A_i, A_j để tổng giá trị các số còn lại trong dãy là số chẵn.

Yêu cầu: Hãy đếm số lượng cách chọn 2 chỉ số i, j thoả mãn. Hai cách chọn khác nhau nếu tồn tại một chỉ số khác nhau.

Đọc từ file gồm:

• Dòng 1 chứa số nguyên dương n (n \leq 10^6 )
• Dòng 2 chứa n số nguyên không âm a_1, a_2,..., a_n (a_i \leq 10^9)

Chỉ một dòng duy nhất chứa một số nguyên là số cách chọn 2 chỉ số thoả mãn.