Cho một dãy ~ A ~ gồm ~ n ~ số nguyên dương ~ a_1, a_2,…, a_n ~.

Yêu cầu: Đếm tất cả các cặp chỉ số ~ i, j~ ~(1≤i≤j≤n) ~ sao cho tổng các phần tử liên tiếp từ chỉ số ~ i ~ đến chỉ số ~ j ~ có trong dãy ~ A~ là một số chẵn. ( ~ S_{i,j}=a_i+a_{i+1}+…+a_{j-1}+a_j ~ là số chẵn)

Dữ liệu vào:

• Dòng đầu chứa duy nhất số nguyên dương ~ n~ ~(1≤n≤10^6) ~
• Dòng thứ ~ i ~ trong ~ n ~ dòng tiếp theo chứa một số ~ a_i~ ~(1≤a_i≤10^9) ~

Kết quả:

• Ghi một số nguyên dương duy nhất là đáp án của bài toán

Ví dụ:

Input

4
2
5
6
8 

Ouput:

4 

Giải thích ví dụ:

Có tất cả 4 cặp chỉ số ~ (i,j) ~ khác nhau thỏa mãn điều kiện bài toán: ~ (1,1)~;~(3,3)~;~(3, 4)~;~(4,4) ~

Ràng buộc dữ liệu:

• ~ 20% ~ tests ứng với ~ 1≤n≤10^2;1≤a_i≤10^9 ~
• ~ 20% ~ tests ứng với ~ 1≤n≤10^3;1≤a_i≤10^9 ~
• ~ 60% ~ tests ứng với ~ 1≤n≤10^6 ~;~ 1≤a_i≤10^9 ~