5727 - GESP:2025-3月等级6-T2-环线
Time Limit : 1 秒
Memory Limit : 128 MB
小 A 喜欢坐地铁。地铁环线有 n个车站，依次以1,2,...n 标号。车站 i（1<=i < n)）的下一个车站是车站i+1 。特殊地，车站n 的下一个车站是车站1。 小 A 会从某个车站出发，乘坐地铁环线到某个车站结束行程，这意味着小 A 至少会经过一个车站。小 A 不会经过一个车站多次。当小 A 乘坐地铁环线经过车站i时，小 A 会获得ai 点快乐值。请你安排小 A 的行程，选择出发车站与结束车站，使得获得的快乐值总和最大
Input
第一行，一个正整数 n。
第二行， n个整数 a1,a2,...an。
Output
一行，一个整数，表示小 A 能获得的最大快乐值。
Examples
Input
4 -1 2 3 0
Output
5
Input
5 -3 4 -5 1 3
Output
5
Hint
数据范围 对于 20% 的测试点，保证 1<=n<=200。
对于 40% 的测试点，保证 1<=n<=2000。
对于所有测试点，保证1<=n<=2 * 10^5 ，-10^9<=ai<=10^9 。