又一个区间游戏

• 时间限制：1.5 秒
• 内存限制：512 MiB

题目描述

给定整数数组。Alice 选择一个非空连续区间，Bob 再从中删除一个元素并使剩余元素和最小。Alice 希望最终得分最大。输出双方最优策略下的得分。

输入格式

第一行是 $n$，第二行是 $n$ 个整数 $a_i$。

输出格式

输出最大得分。

样例输入 1

5
5 -2 10 -1 4

样例输出 1

6

数据范围

• $1\le n\le10^5$；
• $-30\le a_i\le30$。

本题采用独立测试点计分，每个测试点等分。