题目描述
给定 $n$ 个整数 $a_1,a_2,\cdots,a_n$，它们组成了一个圆环。请在这个圆环上，找出一段连续的区间，使得这段区间的数字之和达到最大。空集和圆环本身都可以算圆环的子区间。由于是圆环，$a_n$ 和 $a_1$ 也被视作是相邻的。
输入
第一行：单个整数 $n$。
第二行：$n$ 个整数表示 $a_1$ 到 $a_n$。
输出
单个整数：表示最大的子区间之和。
样例输入输出
提示
+ 对于$30\%$的数据，$1\leq n\leq 100$；
+ 对于$60\%$的数据，$1\leq n\leq 1000$；
+ 对于$100\%$的数据，$1\leq n\leq 100000$；
+ $-1000\leq a_i\leq 1000$。
样例1说明:1+5+3+1是最大的