Cho một dãy ~a~ gồm ~n~ số nguyên không âm ~a_1, a_2, ..., 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ò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, ..., 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.

Output

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

Sample Input 1

5
1 6 6 13 8

Sample Output 1

9

Subtasks

• Có 40% số test ứng 40% số điểm của bài với ~n \le 10^3~;
• Có 30% số test ứng 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 30% số điểm của bài không có thêm ràng buộc.