题目描述

玛丽亚梦想着有一天能成为一个有钱女孩。为了让她的愿望成真，作者把她放上了一条通往成功的道路：一个由 N 个非零整数组成的序列 A。

不过，财富来自辛勤劳动，作者不会让玛丽亚绕过这条资本主义教条。

玛丽亚可以执行如下操作：如果她当前位于位置 pos，那么她可以“跳”到位置 pos + k，其中 k > 1。

当她连续进行了若干次相同长度 k 的跳跃（记跳跃次数为 t），并最终到达位置 new 时，她会停下来休息，并获得

列弗（leva，保加利亚货币单位）。

请注意：她可以进行若干次相同长度的跳跃（比如 5 次），但在中途某处停下来休息（比如在第 2 次之后）。那么她会分别获得两次休息对应的钱（例如 2 × A_i + 3 × A_j），而不是 5 × A_j。

你并不关心玛丽亚，但你觉得这个场景在优化意义上很有趣。请你求出：如果玛丽亚从位置 1 出发，并在位置 N 结束，那么她最多能获得多少列弗。

任务要求

请编写程序 jumps，实现函数 max_prize。你的程序将与评测程序一起编译，并需要正确解决上述问题。

实现细节

你需要实现如下函数：

long long max_prize(std::vector<int> A);

该函数只会被评测程序调用一次，参数即为序列 A。

你的程序文件应命名为 jumps.cpp，其中可以包含你所需的其他代码和函数，但不能包含主函数 main。同时，你不能从标准输入读入，也不能向标准输出输出。

程序必须通过预处理指令包含头文件：

#include "jumps.h"

限制

• 3 ≤ N ≤ 2 × 10^5
• 1 ≤ |A_i| ≤ 10^9

示例

输入

5
1 2 -1 3 100

输出

200

说明

最优方案是以长度为 2 跳两次，经过位置 1 -> 3 -> 5，于是得到

完全合法的另一种做法是：先跳到位置 3，亏掉 1 列弗；再在位置 5 得到 100 列弗，总共 99 列弗。

但这不是最优解。

不能按 1 -> 2 -> 3 -> 4 -> 5 的方式跳，因为那样每次跳跃长度都是 1，这是不允许的。

子任务

某个子任务的分数只有在该子任务下的所有测试都通过时才能获得。