题目背景

有n个数围成一圈，现在梦梦想要从中选择若干个连续的数（每个数最多只能选择一次）加起来，请问能形成的最大的和是多少呢？

输入格式

第一行一个数n。 第二行输入n个数字。

输出格式

一行一个数表示答案。

数据范围

对于40%的数据，$1\leq{N}\leq300$；

对于60%的数据，$1\leq{N}\leq2000$；

对于100%的数据，$1\leq{N}\leq100000$，答案在longint范围内；

样例

8
2 -4 6 -1 -4 8 -1 3

14

时间空间限制

1000ms，262144K