给定一个长度为 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 。

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

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

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

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

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