Tổng dãy

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

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

• \(1 \le i \le j \le n\);
• \(a_i + a_{i+1} + \dots + 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, \dots, a_n\) (\(1 \le a_i \le 10^9\), \(i = 1, 2, \dots, n\)).

Output

• Ghi ra số lượng cặp \((i, j)\) thỏa mãn yêu cầu của bài.

Input

%
5
1 2 3 4 5

Output

%
6

Notes

Trong ví dụ thứ nhất, các cặp thỏa mãn là: \((1, 3)\), \((1, 4)\), \((2, 5)\), \((3, 5)\), \((2, 2)\), \((4,4)\).

Scoring

• (40%) \(n \le 10^2\);
• (40%) \(10^2 < n \le 5 \cdot 10^3\);
• (20%) Không có ràng buộc thêm.