Lan rất hứng thú với tỉ lệ chẵn lẻ tối giản của mảng. $f(x)$ biểu thị tỉ lệ chẵn lẻ tối giản của mảng $x$, ví dụ:

• $f([1,2,3,4])=1:1$, nghĩa là tỉ số tối giản giữa số lượng số lẻ và số lượng số chẵn trong mảng $[1,2,3,4]$ là $1:1$;
• $f([2,4,6])=0:1$;
• $f([1,3,5])=1:0$.

Bây giờ cho một mảng a có độ dài n, Lan muốn biết tồn tại bao nhiêu cặp <i,j> thỏa mãn các tính chất sau:

$1. 1≤i<j≤n$; $2. f([a[1]...a[i]])=f([a[j]...a[n]])$, tức là tỉ lệ chẵn lẻ tối giản của $[a[1]...a[i]]$ bằng tỉ lệ chẵn lẻ tối giản của $[a[j]...a[n]]$.

Dữ liệu vào

Dòng đầu tiên là số nguyên dương $n$, dòng thứ hai gồm $n$ số nguyên dương biểu thị mảng $a$.

Dữ liệu ra

In ra đúng một dòng chứa một số nguyên, biểu thị đáp án.

Ví dụ

Input

6
1 2 3 4 5 6

Output

3

Ghi chú

Giải thích ví dụ

Ví dụ có tổng cộng ba trường hợp sau:

• Cặp $<2,3>$: $f([1,2])=f([3,4,5,6])=1:1$;
• Cặp $<2,5>$: $f([1,2])=f([5,6])=1:1$;
• Cặp $<4,5>$: $f([1,2,3,4])=f([5,6])=1:1$.

Phạm vi dữ liệu

• Với 50% dữ liệu chấm, $1≤n≤10^3, 1≤a[i]≤10^9$;
• Với 100% dữ liệu chấm, $1≤n≤10^5, 1≤a[i]≤10^9$.