Problem E: PIPI奇遇记

Problem E: PIPI奇遇记

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 220  Solved: 70
[Submit] [Status] [Web Board] [Creator:]

Description

武林高手PIPI一生都醉心于修炼武功秘籍。一天它在闲逛时误入一个山洞,好奇的PIPI一直往里面走啊走,终于发现一道石门。
推开石门进入密室,PIPI大喜,里面竟然摆满了内功心法!!
心法被摆放在密室的四周,形成一个环。PIPI注意到密室上方写道“有缘人,你可取心法秘籍修习,不过只能拿走其中连续的几本,否则后果不堪设想”。
PIPI还发现不是每一本心法都能提升内力,若修习方向不同甚至会使内力锐减。
PIPI想要你帮它算算,它最多能提升多少内力值呢?

Input

多组数据
第一行为一个n,表示一共n本心法。1<=n<=100000
接下来n个整数,表示每本心法能够提升的内力值。 -10^9<=内力值<=10^9.

Output

输出PIPI最多能提升多少内力值。

Sample Input

3
1 -2 1
3
-7 8 2
3
-1 -2 -3

Sample Output

2
10
0