CF1320A Journey Planning

Tanya 想要在 Berland 的城市间进行一次旅行。Berland 有 $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 \times 10^5$），表示 Berland 的城市数量。 第二行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$1 \le b_i \le 4 \times 10^5$），其中 $b_i$ 表示第 $i$ 个城市的美丽值。

输出一个整数，表示 Tanya 能选择的旅程的最大美丽值。

第一个样例中最优的旅行方案为 $c = [2, 4, 5]$。 第二个样例中最优的旅行方案为 $c = [1]$。 第三个样例中最优的旅行方案为 $c = [3, 6]$。 由 ChatGPT 4.1 翻译