暂无测试数据。

题目描述

给定一个数列 \(\{a_n\}\)，每次选取其最前面 \(k(k\ge 2)\) 项，获得 \(\sum\limits_{i=1}^ka_i\) 分，然后将这些数换成 \(\sum\limits_{i=1}^ka_i\) ，可以随时停止，求最大得分 \(\text{Score}\)。

输入格式

第一行一个整数 \(n\)，表示数列长度。

接下来 \(n\) 个数 \(a_i\)，表示数列 \(\{a_n\}\)。

输出格式

仅一行，即最大得分 \(\text{Score}\)。

输入输出样例

Sample Input 1

5
2 -1 -1 2 -4

Sample Output 1

3

说明/提示

样例 1 解释

• 第一次，选择 \([\underline{2,-1},-1,2,-4]\)，\(\text{Score}=1\)，数列变成 \([1,-1,2,-4]\)。
• 第二次，选择 \([\underline{1,-1,2},-4]\)，\(\text{Score}=3\)，数列变成 \([2,-4]\)。
• 结束游戏。

所以输出 \(3\)。

样例 2

见附加文件中 card2.in 与 card2.ans。

数据规模与约定

对于 \(100\%\) 的数据，有 \(2\le n\le 10^5\)，且 \(a_i\) 在 long long 范围内。