【题目描述】

小灰灰有一个长度为 $n$ 的序列，第 $i$ 个数为 $a_i$。

小蓝最近在研究子段和，她想知道小灰灰这个序列中，绝对值最小的非空子段和是多少。

具体地，你需要找到一对下标 $l,r$，满足 $1\le l\le r\le n$，使得

$$\left|a_l+a_{l+1}+\cdots+a_r\right|$$

尽可能小，并输出这个最小值。

---

【输入描述】

第一行输入一个整数 $n$。

第二行输入 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

保证：

• $1\le n\le 3\times 10^5$；
• $|a_i|\le 10^6$。

---

【输出描述】

输出一行一个整数，表示绝对值最小的非空子段和。

---

【样例 1】

【样例 1 输入】

5
3 -4 2 6 -3

【样例 1 输出】

1

【样例 1 解释】

可以选择子段 $[1,3]$，它的和为 $3+(-4)+2=1$，绝对值为 $1$。

可以验证不存在和为 $0$ 的非空子段，所以不存在绝对值更小的非空子段和，答案为 $1$。

---

【样例 2】

【样例 2 输入】

6
-10 -20 -30 17 18 19

【样例 2 输出】

4

【样例 2 解释】

可以选择子段 $[2,6]$，它的和为 $(-20)+(-30)+17+18+19=4$，绝对值为 $4$。

可以验证不存在绝对值小于 $4$ 的非空子段和，因此答案为 $4$。

---

【样例 3】

见选手目录下的 Data/sample3.in 和 Data/sample3.ans。

该样例满足 $n\le 100$。

---

【样例 4】

见选手目录下的 Data/sample4.in 和 Data/sample4.ans。

该样例满足 $n\le 5000$。

---

【样例 5】

见选手目录下的 Data/sample5.in 和 Data/sample5.ans。

该样例无特殊性质。

---

【数据规模与约定】

测试点编号	分数	特殊性质
1	5	$a_i > 0$
2	5`	$a_i < 0$
3 ~ 5	15	$n\le 100$
6 ~ 10	25	$n\le 5000$
11 ~ 15	50	无

点击下载本题选手目录