Given an integer array arr, select a subsequence such that for every pair of selected elements, the difference between their values is equal to the difference between their indices.

In other words, for any two selected elements at indices i and j:

|arr[i] - arr[j]| = |i - j|

Find the maximum possible sum of the selected elements.

Example

arr = [1, 5, 4, 3, 7, 8]

Suppose we select:

5 at index 1
3 at index 3

Then:

Value difference = |5 - 3| = 2
Index difference = |1 - 3| = 2

So these two elements can belong to the same valid subsequence.

We need to find the valid subsequence having the maximum sum.

Another Observation

For selected indices i < j:

arr[i] - arr[j] = i - j

Rearranging:

arr[i] - i = arr[j] - j

So, for indices in increasing order, all selected elements must have the same value of arr[i] - i.

Output

Return the maximum sum of a valid subsequence.

Example

Input:
arr = [1, 5, 4, 3, 7, 8]

For each index:

i       0  1  2  3  4  5
arr[i]  1  5  4  3  7  8
arr[i]-i
        1  4  2  0  3  3

The group with arr[i] - i = 3 contains:

7 at index 4
8 at index 5

Their sum is:

7 + 8 = 15

Therefore:

Answer = 15

Constraints

1 ≤ n ≤ 2 × 10^5
-10^9 ≤ arr[i] ≤ 10^9

Note: A single element is also considered a valid subsequence.