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<=i<=j<=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.

Dữ liệu:

• Dòng 1 chứa số nguyên dương \(n\) \((n ≤ 10^{12})\)
  
• Dòng 2 chứa \(n\) số nguyên không âm \(A_1, A_2, ..., A_n\) \((A_i <= 10^3)\)
  

Kếtquả:

• 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.
  

input

5
1 2 3 4 5

output

6

Giải thích ví dụ:

Có \(6\) cách chọn \(2\) chỉ số \(i, j\) là: \(i = 1, j = 2\) tổng còn lại \(A_3 + A_4 + A_5 = 3 + 4 +5 = 12\) là số chẵn.

Tương tự ta có các cặp: \((1,4); (2,3); (2, 5); (3, 4)\) và \((4, 5)\)