Cho dãy $n$ số nguyên không âm $a_1,a_2,\ldots,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 \leq n \leq 10^6$);
• Dòng thứ hai chứa $n$ số nguyên không âm $a_1,a_2,\ldots,a_n$ ($0 \leq a_i \leq 10^9$, $1 \leq i \leq 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\%$): $2 \leq n \leq 1000$;
• Subtask 2 ($30\%$): $1000 < n \leq 2\times 10^4$;
• Subtask 3 ($20\%$): $2 \times 10^4 < n \leq 10^6$.

Example

5
1 2 3 4 5

6

5
2 4 6 8 10

10