Question
Balanced Subarrays
You are given an array A of N integers.
A subarray is called balanced if the number of even elements in the subarray is equal to the number of odd elements.
Your task is to count the total number of balanced subarrays in the array A.
Input
The first line contains a single integer KaTeX can only parse string typed expression — the size of the array.
The second line contains KaTeX can only parse string typed expression integers KaTeX can only parse string typed expression.
The second line contains KaTeX can only parse string typed expression integers KaTeX can only parse string typed expression.
Output
Print a single integer — the number of balanced subarrays.
Example
Input
5
2 3 5 6 4
Output
4
Explanation
Balanced subarrays are: [2, 3], [2, 3, 5, 6], [3, 5], and [5, 6].
Total balanced subarrays = 4.
5
2 3 5 6 4
Output
4
Explanation
Balanced subarrays are: [2, 3], [2, 3, 5, 6], [3, 5], and [5, 6].
Total balanced subarrays = 4.