A. Journey Planningtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputTanya wants to go on a journey across the cities of Berland. There are n cities situated along the main railroad line of Berland, and these cities are numbered from 1 to n. Tanya plans her journey as follows. First of all, she will choose some city c_1 to start her journey. She will visit it, and after that go to some other city c_2 > c_1, then to some other city c_3 > c_2, and so on, until she chooses to end her journey in some city c_k > c_{k - 1}. So, the sequence of visited cities [c_1, c_2, \dots, c_k] should be strictly increasing.There are some additional constraints on the sequence of cities Tanya visits. Each city i has a beauty value b_i associated with it. If there is only one city in Tanya's journey, these beauty values imply no additional constraints. But if there are multiple cities in the sequence, then for any pair of adjacent cities c_i and c_{i + 1}, the condition c_{i + 1} - c_i = b_{c_{i + 1}} - b_{c_i} must hold.For example, if n = 8 and b = [3, 4, 4, 6, 6, 7, 8, 9], there are several three possible ways to plan a journey:  c = [1, 2, 4];  c = [3, 5, 6, 8];  c = [7] (a journey consisting of one city is also valid). There are some additional ways to plan a journey that are not listed above.Tanya wants her journey to be as beautiful as possible. The beauty value of the whole journey is the sum of beauty values over all visited cities. Can you help her to choose the optimal plan, that is, to maximize the beauty value of the journey?InputThe first line contains one integer n (1 \le n \le 2 \cdot 10^5) — the number of cities in Berland.The second line contains n integers b_1, b_2, ..., b_n (1 \le b_i \le 4 \cdot 10^5), where b_i is the beauty value of the i-th city.OutputPrint one integer — the maximum beauty of a journey Tanya can choose.ExamplesInput
6
10 7 1 9 10 15
Output
26
Input
1
400000
Output
400000
Input
7
8 9 26 11 12 29 14
Output
55
NoteThe optimal journey plan in the first example is c = [2, 4, 5].The optimal journey plan in the second example is c = [1].The optimal journey plan in the third example is c = [3, 6].
6
10 7 1 9 10 15

26 
['data structures', 'dp', 'greedy', 'math', 'sortings', '*1400']