题目描述

给定 $n$ 个整数 $a_1,a_2,\cdots,a_n$，它们组成了一个圆环。请在这个圆环上，找出一段连续的区间，使得这段区间的数字之和达到最大。空集和圆环本身都可以算圆环的子区间。由于是圆环，$a_n$ 和 $a_1$ 也被视作是相邻的。

输入格式

第一行：单个整数 $n$。 第二行：$n$ 个整数表示 $a_1$ 到 $a_n$。

输出格式

单个整数：表示最大的子区间之和。

5
3 1 -4 1 5

10

样例解释 1

1+5+3+1是最大的

数据范围

• 对于$30\%$的数据，$1\leq n\leq 100$；
• 对于$60\%$的数据，$1\leq n\leq 1000$；
• 对于$100\%$的数据，$1\leq n\leq 100000$；
• $-1000\leq a_i\leq 1000$。