传统题 1000ms 256MiB

排位复盘

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

赛季末的无限超弦冲刺期,瑞格和队友纪光一起在卡拉彼丘里冲分。每次对局结束后,纪光都会帮瑞格复盘:他记下瑞格每一场排位结束后的分数变化——胜利加分记为正数,失败扣分记为负数。

现在纪光拿到了瑞格连续 nn 场比赛的分数变化记录

d1,d2,…,dn.d_1,d_2,\ldots,d_n.

瑞格的初始分数为 p0=0p_0=0。第 kk 场比赛结束后的分数为

pk=∑i=1kdi(1≤k≤n).p_k=\sum_{i=1}^{k}d_i\qquad(1\le k\le n).

纪光想知道:从初始时刻到第 nn 场比赛结束,瑞格的分数在整个过程中出现过的最低值是多少。也就是说,请求出

min⁡0≤k≤npk.\min_{0\le k\le n}p_k.

由于复盘工具允许透支显示,过程中的分数可以为负。

输入格式

第一行输入一个整数 nn(1≤n≤1051\le n\le 10^5),表示比赛场数。

第二行输入 nn 个整数 d1,d2,…,dnd_1,d_2,\ldots,d_n(−109≤di≤109-10^9\le d_i\le 10^9),整数之间用空格分隔,表示每场比赛结束后的分数变化。

输出格式

输出一行一个整数,表示从初始时刻到第 nn 场结束的整个过程中出现过的最低分数。

样例

5
3 -5 2 -7 6
-7

提示

样例中的分数变化过程依次为

0,3,−2,0,−7,−1.0,3,-2,0,-7,-1.

其中最低分数出现在第 44 场结束后,为 −7-7。

注意初始时刻的分数 00 也参与比较。如果所有分数变化都是正数,那么答案就是 00。

下载正式赛最终版 PDF 题面