1179 - 环形子数组的最大和

通过次数

4

提交次数

12

Time Limit : 1 秒
Memory Limit : 128 MB

给定一个长度为 n 的环形整数数组 a ,输出 a 的非空 子数组 的最大可能和 。

环形数组 意味着数组的末端将会与开头相连呈环状。形式上, a[i] 的下一个元素是 a[(i + 1) % n] , a[i] 的前一个元素是 a[(i - 1 + n) % n] 。

子数组 最多只能包含 a 中的每个元素一次。

对于子数组 a[i], a[i + 1], ..., a[j] ,不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。

Input

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

第二行有 n 个整数,第 i 个整数表示序列的第 i 个数字a_i

Output

输出一行一个整数表示答案。

Examples

Input

4
1 -2 3 -2

Output

3

Hint

1 \leq n \leq 3 \times 10^4

-3 \times 10^4 \leq nums[i] \leq 3\times 10^4