Question
Count Subarrays with Given Zero-One Difference
You are given a binary array of size KaTeX can only parse string typed expression, where each element is either KaTeX can only parse string typed expression or KaTeX can only parse string typed expression, and an integer KaTeX can only parse string typed expression. Your task is to count the number of subarrays such that the difference between the number of zeroes and the number of ones in the subarray is exactly KaTeX can only parse string typed expression.
Input
The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the size of the array and the required difference.
The second line contains KaTeX can only parse string typed expression integers, representing the elements of the array — KaTeX can only parse string typed expression — each being either KaTeX can only parse string typed expression or KaTeX can only parse string typed expression.
The second line contains KaTeX can only parse string typed expression integers, representing the elements of the array — KaTeX can only parse string typed expression — each being either KaTeX can only parse string typed expression or KaTeX can only parse string typed expression.
Output
Print a single integer — the number of subarrays where the difference between the count of zeroes and ones is exactly KaTeX can only parse string typed expression.
Example
Input
5 1
0 1 0 0 1
Output
7
Explanation
Valid subarrays where (number of zeroes − number of ones = 1):
[0] → 1 zero, 0 ones → difference = 1
[0, 1, 0] → 2 zeroes, 1 one → difference = 1
[1, 0, 0] → 2 zeroes, 1 one → difference = 1
[0] (at index 2) → 1 zero, 0 ones → difference = 1
[0] (at index 3) → 1 zero, 0 ones → difference = 1
[0, 0, 1] → 2 zeroes, 1 one → difference = 1
[0, 1, 0, 0, 1] → 3 zeroes, 2 one → difference = 1
Total = 7 subarrays.
5 1
0 1 0 0 1
Output
7
Explanation
Valid subarrays where (number of zeroes − number of ones = 1):
[0] → 1 zero, 0 ones → difference = 1
[0, 1, 0] → 2 zeroes, 1 one → difference = 1
[1, 0, 0] → 2 zeroes, 1 one → difference = 1
[0] (at index 2) → 1 zero, 0 ones → difference = 1
[0] (at index 3) → 1 zero, 0 ones → difference = 1
[0, 0, 1] → 2 zeroes, 1 one → difference = 1
[0, 1, 0, 0, 1] → 3 zeroes, 2 one → difference = 1
Total = 7 subarrays.