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.</p>

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.

Input

• Dữ liệu được đọc từ file văn bản XOASO.INP.
• 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.

Output

• Ghi kết quả ra file văn bản XOASO.OUT.
• Ghi ra 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

Example input 1

5
1 2 3 4 5

Example output 1

6

Example input 2

5
2 4 6 8 10

Example output 2

10