C. 选取石子

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

给定 n 个石子,编号为 1∼n。其中第 i 个石子的价值为 ai。

你需要从中任意挑选若干个石子,并将挑选好的石子按照编号从小到大的顺序排成一排。

选中的石子在排好序后需要满足,对于任意两个相邻的石子(不妨设它们的编号为 x,y),x−y=ax−ay 均成立。

例如,当有 n=8 个石子,石子价值分别为 [3,4,4,6,6,7,8,9] 时,一些合理的选择方案如下:

  • 选择 1,2,4 号石子,它们的价值分别为 3,4,6。1 号石子与 2 号石子相邻,2−1=4−3 成立。2 号石子与 4 号石子相邻,4−2=6−4 成立。所以方案合理。
  • 选择 7 号石子。可以只选择一个石子,此时选取任何石子均为合理方案。

你的选择方案不仅需要合理,而且还要使得选中石子的价值总和尽可能大。

请计算并输出价值总和的最大可能值。

输入格式

第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,an。

输出格式

一个整数,表示选中石子的价值总和的最大可能值。

样例

输入样例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

数据范围与提示

前三个测试点满足 1≤n≤10

全部测试点满足 1≤n≤2×10^5,1≤ai≤4×10^5