题目描述
地铁环线有n个车站，编号1到n，车站i的下一个车站是i+1（车站n的下一个车站是1）。小A从某个车站出发，经过若干车站后结束行程，每个车站只能经过一次。经过车站i时获得快乐值ai。求小A能获得的最大快乐值。

输入格式
第一行：一个正整数n，表示车站数量。
第二行：n个整数ai，表示每个车站的快乐值。

输出格式
一个整数，表示最大快乐值。

样例1
输入：

4  
-1 2 3 0  

输出：

5  

样例2
输入：

5
-3 4 -5 1 3 

输出：

5  

数据范围
对于20%的测试点，保证 (1 ≤ n ≤ 200)
对于40%的测试点，保证(1 ≤ n ≤ 2000)
对于所有节点，保证1 ≤ n ≤2*$10^5$,-$10^9$≤ai≤$10^{9}$