题目描述

对于给定的整数序列 $A={a_1,a_2,…,a_n}$ ，找出两个不重合连续子段，使得两子段中所有数字的和最大。

我们如下定义函数 $d(A)：d(A)=max_{1≤s1≤t1<s2≤t2≤n} \ {\sum_{i=s_1}^{t_1} a_i+\sum_{j=s_2}^{t_2} a_j} $ 我们的目标就是求出 $d(A)$。

输入

第一行是一个整数$n$

第二行一共$n$个整数

输出

输出$d(A)$的值

10
1 -1 2 2 3 -3 4 -4 5 -5

13

样例解释

在样例中，我们取${2,2,3,-3,4}$和${5}$两个子段，即可得到答案。

提示

$1\leq n \leq 10^5$

$-1000 \leq 整数 \leq 1000$