坦尼娅想要踏上穿越伯兰各城市的旅程。贝尔兰的主要铁路线上有 $$$n$$$ 个城市,这些城市的编号从 $$$1$$$ 到 $$$n$$$。
Tanya 计划她的旅程如下。首先,她会选择某个城市$$$c_1$$$开始她的旅程。她将访问它,然后前往其他城市 $$$c_2 > c_1$$$,然后前往其他城市 $$$c_3 > c_2$$$,依此类推,直到她选择在某个城市 $$$c_k > c_{k - 1}$$$ 结束旅程。因此,访问城市的序列 $$$[c_1, c_2, \dots, c_k]$$$ 应该严格递增。
Tanya 访问城市的顺序还有一些额外的限制。每个城市 $$$i$$$ 都有一个与之相关的美丽值 $$$b_i$$$。如果 Tanya 的旅程中只有一座城市,那么这些美丽值就意味着没有额外的限制。但如果序列中有多个城市,则对于任意一对相邻城市 $$$c_i$$$ 和 $$$c_{i + 1}$$$,条件 $$$c_{i + 1} - c_i = b_{c_{i + 1}} - b_{c_i}$$$ 必须成立。
例如,如果 $$$n = 8$$$ 且 $$$b = [3, 4, 4, 6, 6, 7, 8, 9]$$$,则有以下三种可能的方式来规划旅程:
- $$$c = [1, 2, 4]$$$;
- $$$c = [3, 5, 6, 8]$$$;
- $$$c = [7]$$$(包含一个城市的旅程也有效)。
还有一些上面未列出的其他方法来计划旅程。
Tanya 希望她的旅程尽可能美好。全程美感值是所有访问过的城市美感值之和。你能帮助她选择最优的方案,即最大化旅程的美丽价值吗?
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — Berland 的城市数量。
第二行包含 $$$n$$$ 整数 $$$b_1$$$, $$$b_2$$$, ..., $$$b_n$$$ ($$$1 \le b_i \le 4 \cdot 10^5$$$),其中 $$$b_i$$$ 是第 $$$i$$$ 个城市的美丽值。
输出
打印一个整数——Tanya 可以选择的旅程的最大美感。
示例
输入 #1
6 10 7 1 9 10 15
输出 #1
26
输入 #2
1 400000
输出 #2
400000
输入 #3
7 8 9 26 11 12 29 14
输出 #3
55
注意
第一个示例中的最佳行程计划是 $$$c = [2, 4, 5]$$$。
第二个示例中的最佳行程计划是 $$$c = [1]$$$。
第三个示例中的最佳行程计划是 $$$c = [3, 6]$$$。