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 $\frac{P \cdot (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 $START_i$. Then the following should hold:

$START_i \lt START_{i+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 \le N \le 10^5$

$-10^9 \le A_i \le 10^9$