← 返回题目列表

Codeforces · 1320/A

A. 旅程规划

中文机器翻译题面 查看原题

坦尼娅想要踏上穿越伯兰各城市的旅程。贝尔兰的主要铁路线上有 $$$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]$$$。