零和之上

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

给定长度为 $n$ 的整数数组 $a$。选择若干个两两不相交的非空连续区间，要求每个被选区间的元素和均不小于 $0$。最大化所有被选区间的长度之和。

允许不选择任何区间，此时总长度为 $0$。

输入格式

第一行一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出可选区间总长度的最大值。

样例输入 1

5
3 -3 -2 5 -4

样例输出 1

4

样例输入 2

10
5 -2 -4 -6 2 3 -6 5 3 -2

样例输出 2

9

样例输入 3

4
-1 -2 -3 -4

样例输出 3

0

数据范围

$1\le n\le 2\times 10^5$，$-10^9\le a_i\le 10^9$。