题目描述

小杨过生日，妈妈做了一个环形的大蛋糕。蛋糕被切成了 $n$ 块，首尾相接围成一圈，第 $i$ 块的甜度是 $a_i$。

小杨想从蛋糕上取走连续的一段（也可以是一整圈），让取走的蛋糕甜度总和尽可能大。

因为蛋糕是环形的，所以第 $1$ 块和第 $n$ 块也是相邻的。也就是说，允许取走"末尾若干块 + 开头若干块"这样跨过首尾的一段。

请你算出小杨最多能取走多少甜度。

输入格式

第一行一个整数 $n$，表示蛋糕的块数。

第二行 $n$ 个整数 $a_1, a_2, \cdots, a_n$，表示每一块的甜度，整数之间以空格分隔。

输出格式

输出一行一个整数，表示能取走的最大甜度总和。

5
5 -3 5 -10 2

9

3
-5 -2 -8

-2

4
8 -10 2 3

13

样例说明

样例 $1$：如果只在不跨首尾的连续段里挑，最大是第 $1 \sim 3$ 块，$5 + (-3) + 5 = 7$。但蛋糕是环形的，可以取第 $5, 1, 2, 3$ 块，$2 + 5 + (-3) + 5 = 9$，更大。

样例 $2$：所有甜度都是负数，无论怎么取都不会超过 $0$，只能取甜度最大的那一块，答案是 $-2$。

样例 $3$：取第 $3, 4, 1$ 块跨过首尾，$2 + 3 + 8 = 13$。

数据规模与约定

对于 $40\%$ 的数据，$2 \le n \le 1000$。

对于 $100\%$ 的数据，$2 \le n \le 2 \times 10^5$，$-10^4 \le a_i \le 10^4$。

提示：答案可能超过 $2^{31}-1$，请使用 long long。