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ố $ai (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$