FTY在她的矿场内发现了一个神秘宝库，然而想要打开这个神秘宝库需要解决一个千古难题，题目如下：
给出一个长度为$n$的整数序列$a$，问该序列最小非空子段和是多少。
FTY碍于智商有限实在想不出问题的答案，于是她花费$10^{-10^{10000}}$津巴布韦元雇佣智商高达$-10^{10^{10000}}$的你帮助她解决这个问题，并承诺如果成功打开宝库，将会把宝库中$10^{10^{1000}}$ 分之一的宝藏分给你，现在请你给出问题的答案。
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溢出的问题。