题目描述

给出一个数组 $a_1,a_2,\ldots,a_n$。删除其中一个元素后，求剩余数组的最大连续子段和。

删除的元素可以自由选择，但必须恰好删除一个元素。请输出能够得到的最大连续子段和。

输入格式

第一行，一个正整数 $n$。

第二行，$n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出能够得到的最大连续子段和。

输入输出样例

输入 #1

5
9 5 -6 -10 7

输出 #1

15

数据范围

对于全部数据，$n\le 100000$，$-10000\le a_i\le 10000$。数组 $a$ 中至少有一个正数。删数最大子段和(强数据)

2
1 2

2

5
9 5 -6 -10 7

15

42
5864 2855 -9528 -3166 2426 -3465 -110 -7890 -3151 -8601 4897 -9402 -4695 3 709 -9730 7537 -4496 -3505 -1518 8720 -4608 2892 -5569 -7571 -2820 9482 4719 8919 -1985 8980 -6533 -6646 1817 7870 -8537 7644 6069 5509 -4169 -2471 7338

46543