Description
武林高手PIPI一生都醉心于修炼武功秘籍。一天它在闲逛时误入一个山洞，好奇的PIPI一直往里面走啊走，终于发现一道石门。
推开石门进入密室，PIPI大喜，里面竟然摆满了内功心法！！
心法被摆放在密室的四周，形成一个环。PIPI注意到密室上方写道“有缘人，你可取心法秘籍修习，不过只能拿走其中连续的几本，否则后果不堪设想”。
PIPI还发现不是每一本心法都能提升内力，若修习方向不同甚至会使内力锐减。
PIPI想要你帮它算算，它最多能提升多少内力值呢？
Input
多组数据
第一行为一个n，表示一共n本心法。1<=n<=100000
接下来n个整数，表示每本心法能够提升的内力值。 -10^9<=内力值<=10^9.
Sample Input
3
1 -2 1
3
-7 8 2
3
-1 -2 -3