题目描述

FTY在她的矿场内发现了一个神秘宝库,然而想要打开这个神秘宝库需要解决一个千古难题,题目如下:

给出一个长度为$n$的整数序列$a$,问该序列最小非空子段和是多少。

FTY碍于智商有限实在想不出问题的答案,于是她花费$10^{-10^{10000}}$津巴布韦元雇佣智商高达$-10^{10^{10000}}$的你帮助她解决这个问题,并承诺如果成功打开宝库,将会把宝库中$10^{10^{1000}}$ 分之一的宝藏分给你,现在请你给出问题的答案。


输入格式

第一行一个整数$n(n\leq 10^5)$表示序列的长度。

第二行共$n$个整数,第$i$个整数为$a_i(|a_i|\leq 10^8)$。


输出格式

输出一个整数,表示序列$a$的最小非空子段和。


样例数据

输入

样例输入一
5
1 2 3 4 5

样例输入二
4
-4 -2 -3 -1

样例输入三
5
1 -5 1 -3 2

输出

样例输入一
1

样例输入二
-10

样例输入三
-7

备注

可以使用分治,注意int溢出的问题。


操作

评测记录

优秀代码

信息

时间限制: 1s
内存限制: 128MB
评测模式: Normal

题解