You are given an array A of size N. You need to make a GG array from this array. A GG array is an array of size P⋅(P+1)2, where P is some positive integer.
To make the GG array, you can concatenate some distinct sized and non overlapping sub arrays of A where each subarray can be of size between 1 to P. Distinct sized subarrays means that you cannot take more than 1 subarray whose size is same.
Also let the starting positions of subarray of size i be denoted by STARTi. Then the following should hold:
STARTi<STARTi+1 for all valid i.
Your goal is to maximise the sum of elements in GG array. Can you find the maximum sum possible?
Input:
First line of input contains an integer N denoting the size of A. Next line contains N space separated integers denoting the array A.
Output:
Print the maximum sum of the GG array that you can make from the given array A.
Constraints:
1≤N≤105
−109≤Ai≤109