You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面背景

环上子段和

题目描述

给你一个序列 $a$ ，现在需要你求出它的最大子段和。

需要注意，这是一个首尾相接的环形序列，序列中的数不一定全是正数。

输入格式

第一行一个整数 $n$

第二行 $n$ 个整数表示 $a_i$

输出格式

输出一个整数, 表示最大子段和

样例 #1

样例输入 #1

5
1 2 -3 -4 3

样例输出 #1

6

数据范围

• 对于 $50\%$ 的数据，$1\le n\le 5 \times 10^3$
• 对于 $100\%$ 的数据，$1\le n\le 10^6, -10^6 \le a_i \le 10^6$