← 返回题目列表

Codeforces · 1472/C

C. 跳远

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

Polycarp 在圣诞树下发现了一个由 $$$n$$$ 元素组成的数组 $$$a$$$ 以及使用它的说明:

- 首先,选择索引 $$$i$$$ ($$$1 \leq i \leq n$$$) — 数组中的起始位置。将筹码放在索引 $$$i$$$ 处(值 $$$a_i$$$)。
- 当 $$$i \leq n$$$ 时,将 $$$a_i$$$ 添加到您的分数中,并将筹码 $$$a_i$$$ 位置向右移动(即将 $$$i$$$ 替换为 $$$i + a_i$$$)。
- 如果 $$$i > n$$$,则 Polycarp 结束游戏。

例如,如果 $$$n = 5$$$ 且 $$$a = [7, 3, 1, 2, 3]$$$,则可能有以下游戏选项:

- Polycarp 选择 $$$i = 1$$$。游戏过程:$$$i = 1 \overset{+7}{\longrightarrow} 8$$$。游戏得分为:$$$a_1 = 7$$$。
- 坡旅甲选择 $$$i = 2$$$。游戏过程:$$$i = 2 \overset{+3}{\longrightarrow} 5 \overset{+3}{\longrightarrow} 8$$$。游戏得分为:$$$a_2 + a_5 = 6$$$。
- 坡旅甲选择 $$$i = 3$$$。游戏过程:$$$i = 3 \overset{+1}{\longrightarrow} 4 \overset{+2}{\longrightarrow} 6$$$。游戏得分为:$$$a_3 + a_4 = 3$$$。
- 坡旅甲选择 $$$i = 4$$$。游戏过程:$$$i = 4 \overset{+2}{\longrightarrow} 6$$$。游戏得分为:$$$a_4 = 2$$$。
- 坡旅甲选择 $$$i = 5$$$。游戏过程:$$$i = 5 \overset{+3}{\longrightarrow} 8$$$。游戏得分为:$$$a_5 = 3$$$。

帮助Polycarp找出如果他以最佳方式选择起始索引,他可以获得的最大分数。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。

下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 数组 $$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,在单独的行上输出一个数字——Polycarp 根据语句中的指令在相应数组上玩游戏可以获得的最高分数。请注意,Polycarp 选择从 $$$1$$$ 到 $$$n$$$ 的任何起始位置,以最大化他的结果。

示例

输入 #1

4
5
7 3 1 2 3
3
2 1 4
6
2 1000 2 3 995 1
5
1 1 1 1 1

输出 #1

7
6
1000
5

注意

第一个测试用例在语句中进行了解释。

在第二个测试用例中,通过选择 $$$i = 1$$$ 可以获得最高分数。

在第三个测试用例中,通过选择 $$$i = 2$$$ 可以获得最高分。

在第四个测试用例中,通过选择 $$$i = 1$$$ 可以获得最高分。