Cho một dãy \(A\) gồm \(n\) số nguyên dương \(a_{1},\ a_{2},\ldots,\ a_{n}\).

Yêu cầu: Đếm tất cả các cặp chỉ số \(i,\ j\ (1 \leq i \leq j \leq 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} + \ldots + 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 \leq n \leq 10^{6})\)

+ Dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa một số \(a_{i}\ (1 \leq a_{i} \leq 10^{9})\)

Kết quả: Ghi vào file CAPCS.OUT một số nguyên dương duy nhất là đáp án của bài toán

Ví dụ:

Input	Ouput
4 2 5 6 8	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 \leq n \leq 10^{2};1 \leq a_{i} \leq 10^{9}\)

+ \(20\%\) tests ứng với \(1 \leq n \leq 10^{3};1 \leq a_{i} \leq 10^{9}\)

+ \(60\%\) tests ứng với \(1 \leq n \leq 10^{6}\);\(1 \leq a_{i} \leq 10^{9}\)