You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

秘密武器

在1944年的一个寒冷冬日，盟军情报部门截获了一份神秘的德军电报。电报中提到了一个代号为“环状序列”的秘密武器，据说这种武器能够通过特殊的数学计算，预测盟军的行动路线，从而在战场上占据优势。

为了破解这个秘密，盟军派遣了一位年轻的数学天才——艾米丽，她被赋予了一个艰巨的任务：解开这个“环状序列”的谜题。艾米丽发现，这个序列实际上是一个环状的数字序列，德军希望通过计算其中连续不重叠且非空的两段子段的和，来预测盟军的行动。

艾米丽知道，如果她能找到这个环状序列中最大的两段子段和，就能反推出德军的策略，从而制定出相应的对策。于是，她开始了紧张的计算工作。

题目描述

给出一段长度为 $n$ 的环状序列 $a$，即认为 $a_1$ 和 $a_n$ 是相邻的，选出其中连续不重叠且非空的两段使得这两段和最大。

输入格式

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

第二行有 $n$ 个整数，描述序列 $a$，第 $i$ 个数字表示 $a_i$。

输出格式

一行一个整数，为最大的两段子段和是多少。

样例 #1

样例输入 #1

7
2 -4 3 -1 2 -4 3

样例输出 #1

9

提示

数据规模与约定

对于全部的测试点，保证 $2 \leq n \leq 2 \times 10^5$，$-10^4 \leq a_i \leq 10^4$。