Question
Count Subarrays with Power of Two Difference
You are given a binary array. Your task is to count the number of subarrays such that the absolute difference between the number of KaTeX can only parse string typed expression's and KaTeX can only parse string typed expression's in the subarray is equal to a power of KaTeX can only parse string typed expression.
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, representing the elements of the array — 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.
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, where each element is 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 absolute difference between the count of KaTeX can only parse string typed expression's and KaTeX can only parse string typed expression's is a power of KaTeX can only parse string typed expression.
Example
Input
4
1 0 0 1
Output
7
Explanation
Valid subarrays where the difference between number of 0's and 1's is a power of 2:
Subarray (0, 0) → [1], difference = 1 → valid
Subarray (0, 1) → [1, 0], difference = 0 → not valid
Subarray (0, 2) → [1, 0, 0], difference = 1 → valid
Subarray (0, 3) → [1, 0, 0, 1], difference = 0 → not valid
Subarray (1, 1) → [0], difference = 1 → valid
Subarray (1, 2) → [0, 0], difference = 2 → valid
Subarray (1, 3) → [0, 0, 1], difference = 1 → valid
Subarray (2, 2) → [0], difference = 1 → valid
Subarray (2, 3) → [0, 1], difference = 0 → not valid
Subarray (3, 3) → [1], difference = 1 → valid
Total = 7 valid subarrays.
4
1 0 0 1
Output
7
Explanation
Valid subarrays where the difference between number of 0's and 1's is a power of 2:
Subarray (0, 0) → [1], difference = 1 → valid
Subarray (0, 1) → [1, 0], difference = 0 → not valid
Subarray (0, 2) → [1, 0, 0], difference = 1 → valid
Subarray (0, 3) → [1, 0, 0, 1], difference = 0 → not valid
Subarray (1, 1) → [0], difference = 1 → valid
Subarray (1, 2) → [0, 0], difference = 2 → valid
Subarray (1, 3) → [0, 0, 1], difference = 1 → valid
Subarray (2, 2) → [0], difference = 1 → valid
Subarray (2, 3) → [0, 1], difference = 0 → not valid
Subarray (3, 3) → [1], difference = 1 → valid
Total = 7 valid subarrays.