Cho dãy số nguyên không âm a1, a2, ... an. Người ta muốn chọn hai chỉ số i, j sao cho 1<=i<j<=n và xóa khỏi dãy hai số ai, aj để tổng giá trị các số còn lại trong dãy là số chẵn.</p>

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<=10^6)

• Dòng 2 chứa N số nguyên không âm a1, a2, ... an (1 <= ai<=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 ≤ 1000

Có 50% số test còn lại của bài có 1000 < n ≤ 10^6

Input:

4
3 4 1 2

Output:

2