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

Yêu cầu: Đếm số cặp ~(i, j)~ đồng thời thỏa mãn:

• ~1 \le i < j \le n;~
• ~a_i + a_{i+1} + ... + a_j~ là một số chẵn.

INPUT

Dòng đầu chứa số nguyên dương ~n~ (~2 \le n \le 10^5~);

Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^9; i = 1, 2, ..., n~).

OUTPUT

Số lượng cặp ~(i, j)~ thỏa mãn yêu cầu của bài.

SAMPLE INPUT 1

5
1 2 3 4 5

SAMPLE OUTPUT 1

4

Giải thích: Số cặp thỏa mãn là (~1, 3~), (~1, 4~), (~2, 5~), (~3, 5~).

SAMPLE INPUT 2

4
2 5 6 4

SAMPLE OUTPUT 2

1

SUBTASKS