{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eTanya 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$$$. \u003c/p\u003e\u003cp\u003eTanya 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 \u0026gt; c_1$$$, then to some other city $$$c_3 \u0026gt; c_2$$$, and so on, until she chooses to end her journey in some city $$$c_k \u0026gt; c_{k - 1}$$$. So, the sequence of visited cities $$$[c_1, c_2, \\dots, c_k]$$$ should be strictly increasing.\u003c/p\u003e\u003cp\u003eThere 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\u0027s 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 \u003d b_{c_{i + 1}} - b_{c_i}$$$ must hold.\u003c/p\u003e\u003cp\u003eFor example, if $$$n \u003d 8$$$ and $$$b \u003d [3, 4, 4, 6, 6, 7, 8, 9]$$$, there are several three possible ways to plan a journey:\u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$c \u003d [1, 2, 4]$$$; \u003c/li\u003e\u003cli\u003e $$$c \u003d [3, 5, 6, 8]$$$; \u003c/li\u003e\u003cli\u003e $$$c \u003d [7]$$$ (a journey consisting of one city is also valid). \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eThere are some additional ways to plan a journey that are not listed above.\u003c/p\u003e\u003cp\u003eTanya 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?\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains one integer $$$n$$$ ($$$1 \\le n \\le 2 \\cdot 10^5$$$) — the number of cities in Berland.\u003c/p\u003e\u003cp\u003eThe 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.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint one integer — the maximum beauty of a journey Tanya can choose.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e6\n10 7 1 9 10 15\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e26\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\n400000\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e400000\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7\n8 9 26 11 12 29 14\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e55\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eThe optimal journey plan in the first example is $$$c \u003d [2, 4, 5]$$$.\u003c/p\u003e\u003cp\u003eThe optimal journey plan in the second example is $$$c \u003d [1]$$$.\u003c/p\u003e\u003cp\u003eThe optimal journey plan in the third example is $$$c \u003d [3, 6]$$$.\u003c/p\u003e"}}]}