Question
Levitating Powers
You are given an array of KaTeX can only parse string typed expression integers. Your task is to find the maximum power of KaTeX can only parse string typed expression that can be obtained as the sum of any non-empty subarray of the array.
A subarray is a contiguous part of the array.
If no subarray has a sum equal to a power of KaTeX can only parse string typed expression, print 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 array elements — KaTeX can only parse string typed expression.
The second line contains KaTeX can only parse string typed expression integers representing the array elements — KaTeX can only parse string typed expression.
Output
Print a single integer — the maximum power of KaTeX can only parse string typed expression that appears as the sum of any non-empty subarray.
If no such subarray exists, print KaTeX can only parse string typed expression.
If no such subarray exists, print KaTeX can only parse string typed expression.
Example
Input
5
3 1 2 7 -1
Output
8
Explanation
The subarray KaTeX can only parse string typed expression has sum KaTeX can only parse string typed expression, which is a power of KaTeX can only parse string typed expression.
Other valid subarray sums include:
KaTeX can only parse string typed expression from subarray KaTeX can only parse string typed expression
KaTeX can only parse string typed expression from subarray KaTeX can only parse string typed expression
The maximum power of KaTeX can only parse string typed expression among all valid subarray sums is KaTeX can only parse string typed expression.
5
3 1 2 7 -1
Output
8
Explanation
The subarray KaTeX can only parse string typed expression has sum KaTeX can only parse string typed expression, which is a power of KaTeX can only parse string typed expression.
Other valid subarray sums include:
KaTeX can only parse string typed expression from subarray KaTeX can only parse string typed expression
KaTeX can only parse string typed expression from subarray KaTeX can only parse string typed expression
The maximum power of KaTeX can only parse string typed expression among all valid subarray sums is KaTeX can only parse string typed expression.