题目描述

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

所谓“环状”，是指 $a_1$ 与 $a_n$ 相邻，整个序列首尾相连。

请在这个环上选出两段连续且非空的子段，要求两段互不重叠。求这两段中所有整数之和的最大值。

输入格式

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

第二行有 $n$ 个整数，依次表示 $a_1,a_2,\dots,a_n$。

输出格式

输出一行一个整数，表示最大的两段子段和。

输入输出样例 #1

输入 #1

7
2 -4 3 -1 2 -4 3

输出 #1

9

说明/提示

样例解释

一种最优选法是：

• 选择子段 $[3,5]$，对应元素为 $3,-1,2$，和为 $4$；
• 选择子段 $[7,1]$，对应元素为 $3,2$，和为 $5$。

由于序列是环状的，$[7,1]$ 表示从第 $7$ 个数到第 $1$ 个数这一段。两段互不重叠，总和为：

$4+5=9$

数据规模与约定

对于全部测试点：

$2 \le n \le 2\times 10^5$

$-10^4 \le a_i \le 10^4$