题目描述

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$。

请从中选出两个子段。这里的“子段”指序列中连续且非空的一段。要求：

• 每个子段的长度至少为 $1$；
• 两个子段不能重叠；
• 两个子段之间至少间隔一个数。
  也就是说，如果左侧子段为 $[l_1,r_1]$，右侧子段为 $[l_2,r_2]$，则必须满足
  $r_1+1<l_2$

求这两个子段中所有整数之和的最大值，并输出这个最大值。

输入格式

第一行一个整数 $n$，表示序列长度。

第二行包含 $n$ 个整数，依次表示序列中的每个数。

输出格式

输出一行一个整数，表示所选两个子段中整数总和的最大值。

输入输出样例 #1

输入 #1

5
83 223 -13 1331 -935

输出 #1

1637

输入输出样例 #2

输入 #2

3
83 223 -13

输出 #2

70

说明/提示

样例解释

样例 1：可以选择子段 $[1,2]$ 和 $[4,4]$，和为
$(83+223)+1331=1637$ 两个子段之间隔着第 $3$ 个数 $-13$。

样例 2：只能选择子段 $[1,1]$ 和 $[3,3]$，和为
$83+(-13)=70$

数据规模与约定

• 对于 $30\%$ 的数据，$n\le 100$；
• 对于 $60\%$ 的数据，$n\le 10^4$；
• 对于 $100\%$ 的数据，$n\le 10^6$，$-10^9 \le a_i \le 10^9$