Đếm cặp chỉ số

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

Yêu cầu: Đếm tất cả các cặp chỉ số \(i, j\) \((1 \le i \le j \le n)\) sao cho tổng các phần tử liên tiếp từ chỉ số \(i\) đến chỉ số \(j\) trong dãy \(A\) là một số chẵn.

Cụ thể, ta định nghĩa:
$
S_{ij} = a_i + a_{i+1} + \dots + a_j
$

Yêu cầu: Đếm số lượng cặp \((i, j)\) sao cho \(S_{ij}\) là số chẵn.

Input

Dữ liệu được đọc từ file CPAIR.INP:

• Dòng đầu chứa số nguyên dương \(n\) (\(1 \le n \le 10^6\)) --- số phần tử của dãy \(A\).
• \(n\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(a_i\) (\(1 \le a_i \le 10^9\)) --- phần tử thứ \(i\) của dãy.

Output

Ghi ra file CPAIR.OUT một dòng duy nhất chứa số nguyên --- kết quả bài toán: số lượng cặp \((i, j)\) thoả mãn điều kiện tổng là số chẵn.

Example

4
2
5
6
8

4

Scoring

• 20% test có \(1 \le n \le 10^2\), \(1 \le a_i \le 10^9\)
• 20% test có \(1 \le n \le 10^3\), \(1 \le a_i \le 10^9\)
• 60% test có \(1 \le n \le 10^6\), \(1 \le a_i \le 10^9\)