g6-07936. 最大子段和·至多删除一个元素 未做

给定一个长度为 $n$ 的整数数组 $a_1,a_2,\dots ,a_n$。你可以选择一个非空的连续子段，并从中至多删除一个元素（也可以不删），要求删除后子段不能为空。求剩余元素之和的最大值。

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_i$。

一行一个整数，表示最大和。

输入 1

9
-2 1 -3 4 -1 2 1 -5 4

输出 1

10

解释 1

选择子段 $4,-1,2,1,-5,4$，删除 $-5$，剩下 $4-1+2+1+4=10$。

对于所有数据，$1\le n\le 10^5$，$-10^4\le a_i\le 10^4$；答案在 long long 范围内。