题目描述

小Z在课堂上已经会求“最大子段和”了。

小K继续给他出难题，必须要从数组中任意删去一个数字，再求剩下的最大子段和。

输入格式

第一行，$1$ 个正整数 $n$，表示数组大小

第二行，$n$ 个整数 $a_i$，中间用空格隔开

输出格式

输入输出样例

5
9 5 -6 -10 7

15

样例 $\tt \#1$说明

删除第 $4$ 个数，序列变成 $[9,5,−6,7]$，最大子段和为 $15$。没有更大的方案。

9
5 -12 8 6 -1 -10 1 2 4

20

样例 $\tt \#2$说明

删除第 $6$ 个数，序列变成 $[5, -12, 8, 6, -1, 1, 2, 4]$，最大子段和为 $20$。没有更大的方案。

数据范围

$50\%:2\le n \le100$

$100\%:2\le n\le 10^5,-10^9\le n \le 10^9$