Cho dãy $n$ số nguyên không âm $a_1,a_2,\dots ,a_n$. Người ta tiến hành chọn ra hai chỉ số $i$, $j$ sao cho $i<j$ và xoá khỏi dãy hai 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: Đếm số lượng cách chọn hai 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.

Dữ liệu

Đọc từ file văn bản XOASO.INP có cấu trúc như sau:

• Dòng thứ nhất chứa số nguyên dương $n$ ($2\le n\le {10}^6$);
• Dòng thứ hai chứa $n$ số nguyên không âm $a_1,a_2,\dots ,a_n$ ($0\le a_i\le {10}^9$, $1\le i\le n$). Các số cách nhau bởi dấu cách.

Kết quả

Ghi ra file văn bản XOASO.OUT một số nguyên duy nhất cho biết số cách chọn hai chỉ số $i$, $j$ thoả mãn.

Scoring

• Subtask 1 ($50\mathrm{\%}$): $2\le n\le 1000$;
• Subtask 2 ($30\mathrm{\%}$): $1000<n\le 2\times {10}^4$;
• Subtask 3 ($20\mathrm{\%}$): $2\times {10}^4<n\le {10}^6$.

Example

5
1 2 3 4 5

6

5
2 4 6 8 10

10