Cho dãy ~n~ số nguyên dương ~a_1,a_2,\ldots,a_n~.

Yêu cầu

Đếm số cặp ~(i,j)~ thỏa ~1 \le i < j \le n~ và tổng ~a_i+a_{i+1}+\cdots+a_j~ là số chẵn.

Input

Dòng đầu chứa ~n~ ~(2 \le n \le 10^5)~.

Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~ ~(1 \le a_i \le 10^9)~.

Output

In ra số lượng cặp thỏa mãn.

Subtask

• Subtask 1: ~n \le 10^2~.
• Subtask 2: ~10^2 < n \le 5\cdot 10^3~.
• Subtask 3: Không có ràng buộc bổ sung.

Ví dụ 1

5
1 2 3 4 5

4

Ví dụ 2

4
2 5 6 4

1