Cho số nguyên dương ~n~ và dãy số nguyên không âm gồm ~n~ phần tử ~a_1, a_2, \dots, a_n~. Hãy cho biết có bao nhiêu cách chọn cặp chỉ số ~(i, j)~, trong đó ~(1 \leq i, j \leq n; i \neq j)~ sao cho sau khi xóa 2 phần tử ~a_i, a_j~ 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à 1 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.

Input

• Dòng 1 chứa số nguyên dương ~n~ ~(2 \leq n \leq 10^6)~.
• Dòng 2 chứa ~n~ số nguyên là giá trị của các phần tử ~a_1, a_2, \dots, a_n~ ~(0 \leq a_i \leq 10^6)~.

Output

• In ra một số nguyên là kết quả bài toán.

Sample Input

5 
1 6 3 8 4

Sample Output

4

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; ~a_2 + a_4 + a_5 = 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)~

Subtasks

• Có 50% số test ứng với 50% số điểm thỏa mãn: ~n \leq 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.