Question
Power-of-Two Subarray Sums
You are given an array a of n positive integers. Your task is to count the number of subarrays of a whose sum is a power of two (i.e., the subarray sum equals 2k for some integer k >= 0).
Note:
Note:
- A subarray is a contiguous part of an array, meaning it consists of consecutive elements taken from the original array, preserving their order.
- Example: For array
[1, 2, 3], the subarrays are:[1],[2],[3],[1,2],[2,3],[1,2,3].
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 a — 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 a — KaTeX can only parse string typed expression.
Output
Print a single integer — the number of subarrays whose sum is a power of two.
Example
Input
6
1 2 1 3 2 1
Output
8
Explanation
Number of subarrays with sum 1 → 3.
Number of subarrays with sum 2 → 2.
Number of subarrays with sum 4 → 2:
[1, 2, 1] and [1, 3]
Number of subarrays with sum 8 → 1: [2, 1, 3, 2]
Total = 8.
Input
5
1 1 1 1 1
Output
11
Explanation
Number of subarrays with sum 1 → 5
Number of subarrays with sum 2 → 4
Number of subarrays with sum 4 → 2
Total = 11.
6
1 2 1 3 2 1
Output
8
Explanation
Number of subarrays with sum 1 → 3.
Number of subarrays with sum 2 → 2.
Number of subarrays with sum 4 → 2:
[1, 2, 1] and [1, 3]
Number of subarrays with sum 8 → 1: [2, 1, 3, 2]
Total = 8.
Input
5
1 1 1 1 1
Output
11
Explanation
Number of subarrays with sum 1 → 5
Number of subarrays with sum 2 → 4
Number of subarrays with sum 4 → 2
Total = 11.