⼩ A 喜欢坐地铁 。地铁环线有 n 个车站 ，依次以 1 , 2, , n 标号 。车站 i（ 1 ≤ i < n） 的下一个车站是车站 i + 1 。 特殊地 ，车站 n 的下一个车站是车站 1 。 ⼩ A 会从某个车站出发 ，乘坐地铁环线到某个车站结束⾏程 ，这意味着⼩ A ⾄少会经过一个车站 。⼩ A 不会经过一 个车站多次 。当⼩ A 乘坐地铁环线经过车站 i 时 ，⼩ A 会获得 ai 点快乐值 。请你安排⼩ A 的⾏程 ，选择出发车站与 结束车站 ，使得获得的快乐值总和最⼤ 。
第一⾏ ，一个正整数 n ，表⽰车站的数量。 第⼆⾏ ，n 个整数 a1 , a2 , s an ，分别表⽰经过每个车站时获得的快乐值。
一⾏ ，一个整数 ，表⽰⼩ A 能获得的最⼤快乐值
4 -1 2 3 0
5
数据范围 对于 20% 的测试点 ，保证 1 ≤ n ≤ 200。 对于 40% 的测试点 ，保证 1 ≤ n ≤ 2000。 对于所有测试点 ，保证 1 ≤ n ≤ 2 x 10^5 -10^9 ≤ ai ≤ 10^9 。
