题目描述

婷婷给出长度为 $n$ 的序列 $a$，请你找到四元组 $1 \leq l_1 \leq r_1\lt l_2 \leq r_2 \leq n$，最大化并输出 $[l_1,r_1]$ 和 $[l_2,r_2]$ 内所有元素的和。

输入格式

一行，一个正整数 $n$。

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

输出格式

一行，一个整数，表示答案。

5
83 223 -13 1331 -935

1637

2
1 2

3

2
0 0

0

说明与提示

样例解释

最优解选择 $[1,2]$ 和 $[4,4]$

数据范围

对于 $30\%$ 的数据，$1 \leq n \leq 100$。

对于 $60\%$ 的数据，$1 \leq n \leq 10^4$。

对于 $100\%$ 的数据，$1 \leq n \leq 10^5,0 \leq |a_i| \leq 10^9$。