Cho dãy số nguyên không âm \(a_1, a_2, ... a_n\). Người ta muốn chọn hai chỉ số i, j sao cho \(1 \leq i< j \leq n\) 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: Hãy đế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 vào:

• Dòng 1 chứ số nguyên dương n \((n \leq 10^6)\)
• Dòng 2 chứa N số nguyên không âm \(a_1, a_2, ... a_n\) \((1 \leq a_i \leq 10^6)\)

Dữ liệu ra:

In ra số lượng cách chọn theo yêu cầu đề bài

Ràng buộc:

• Có 50% số test của bài có \(1 < n \leq 1000\)
• Có 50% số test còn lại của bài có \(1000< n \leq 10^6\)

Ví dụ:

Input

4
3 4 1 2

Output

2