Cặp số chẵn

Cho một dãy \(a\) gồm \(n\) số nguyên không âm \(a_1, a_2, \ldots, a_n\).

Yêu cầu: Viết chương trình đếm số lượng cách chọn ra trong dãy \(a\) hai phần tử sao cho tích của hai phần tử đó là một số chẵn.

Input

Dữ liệu vào có cấu trúc như sau:

• Dòng 1: Chứa một số nguyên \(n\) \((2 \le n \le 10^6)\);

• Dòng 2: Chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((0 \le a_i \le 10^{18}\) với \(1 \le i \le n)\), các số cách nhau bởi một dấu cách trống.

Ràng buộc:

• Có \(40\%\) số test ứng với \(40\%\) số điểm của bài với \(n \le 10^3\);

• Có \(30\%\) số test ứng với \(30\%\) số điểm của bài với \(a_i\) chẵn \((1 \le i \le n)\);

• \(30\%\) số test còn lại ứng với \(30\%\) số điểm của bài không có thêm ràng buộc.

Output

In ra một số nguyên duy nhất là số lượng cặp số thỏa mãn yêu cầu đề bài.

Example

Input:

5
1 6 6 13 8

Output:

9

Note

Có \(10\) cách chọn hai phần tử, chỉ cặp \((1, 13)\) có tích lẻ nên đáp án là \(9\).