Mảng Con Chẵn Lẻ

Trong một buổi thực hành nấu ăn, FullHouse Dev được đầu bếp giao cho một thử thách thú vị. Họ phải tìm cách phân tích các phần nguyên liệu sao cho số lượng nguyên liệu có khối lượng chẵn và lẻ gram cân bằng nhau.

Bài toán

FullHouse Dev được cung cấp một mảng \(A\) gồm \(N\) giá trị nguyên dương. Một mảng con của mảng này được gọi là mảng con Chẵn-Lẻ nếu số lượng số lẻ trong mảng con bằng với số lượng số chẵn trong mảng con đó.

Nhiệm vụ của nhóm là tìm ra số lượng mảng con Chẵn-Lẻ có thể tạo được từ mảng đã cho.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(N\) - kích thước của mảng.
• Dòng thứ hai chứa \(N\) số nguyên dương cách nhau bởi dấu cách, biểu diễn các phần tử của mảng \(A\).

OUTPUT FORMAT:

• In ra một số nguyên duy nhất, biểu thị số lượng mảng con Chẵn-Lẻ có thể tạo được.

Ràng buộc:

• \(1 \leq N \leq 10^5\)
• \(1 \leq A[i] \leq 10^9\)

Ví dụ

INPUT

4
1 2 1 2

OUTPUT

4

Giải thích

Gọi \(A[i,j]\) là mảng con của \(A\) bắt đầu từ chỉ số \(i\) và kết thúc ở chỉ số \(j\).

Có bốn mảng con thỏa mãn số lượng số chẵn bằng số lượng số lẻ:

• \(A[1,2]\) chứa một số lẻ và một số chẵn
• \(A[2,3]\) chứa một số lẻ và một số chẵn
• \(A[3,4]\) chứa một số lẻ và một số chẵn
• \(A[1,4]\) chứa hai số lẻ và hai số chẵn