Cho số nguyên dương \(n\) và dãy số nguyên \(a_1,a_2,…,a_n.\)

Yêu cầu: Đếm tất cả các cặp chỉ số \((i,j)\) sao cho tổng \(a_i+a_{i+1}+..+a_j\) là một số chẵn.

Input

• Dòng thứ nhất chứa số nguyên dương \(n(2≤n≤10^6 ).\)

• Dòng thứ \(i\) trong \(n\) dòng tiếp theo nguyên dương \(a_i (|a_i |≤10^9 ).\)

Output

• Ghi một số là số lượng cặp tìm được thỏa bài toán.

Ràng buộc

• Subtask 1: 20% test \(n≤10^2.\)

• Subtask 2: 20% test \(n≤10^3.\)

• Subtask 3: 60% test \(n≤10^6.\)

Sample Input

4
2
5
6
8

Sample Output

4