Question
Subarrays with Sum as Power of Three
You are given an array of KaTeX can only parse string typed expression non-negative integers. Your task is to count the number of subarrays whose sum is equal to a power of KaTeX can only parse string typed expression.
A number is considered a power of KaTeX can only parse string typed expression if it can be written as KaTeX can only parse string typed expression for some integer 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.
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.
Output
Print a single integer — the number of subarrays whose sum is a power of KaTeX can only parse string typed expression.
Example
Input
5
1 2 3 4 5
Output
5
Explanation
Valid subarrays whose sum is a power of KaTeX can only parse string typed expression:
(0) → 1 = KaTeX can only parse string typed expression
(0, 1) → 1 + 2 = 3 = KaTeX can only parse string typed expression
(2, 2) → 3 = KaTeX can only parse string typed expression
(3, 4) → 4 + 5 = 9 = KaTeX can only parse string typed expression
(1, 3) → 2 + 3 + 4 = 9 = KaTeX can only parse string typed expression
Total = 5 subarrays.
5
1 2 3 4 5
Output
5
Explanation
Valid subarrays whose sum is a power of KaTeX can only parse string typed expression:
(0) → 1 = KaTeX can only parse string typed expression
(0, 1) → 1 + 2 = 3 = KaTeX can only parse string typed expression
(2, 2) → 3 = KaTeX can only parse string typed expression
(3, 4) → 4 + 5 = 9 = KaTeX can only parse string typed expression
(1, 3) → 2 + 3 + 4 = 9 = KaTeX can only parse string typed expression
Total = 5 subarrays.