题目描述

给定 $n$ 个整数 $a_1,a_2,\dots,a_n$，请问这个序列最长有多少长的前缀，满足元素的和大于或等于 $0$？如果任何长度大于 $0$ 的前缀之和都为负数，则输出 $0$

输入格式

• 第一行：单个整数表示 $n$
• 第二行：$n$ 个整数表示 $a_1,a_2, \dots, a_n$

输出格式

• 单个整数：表示最长的前缀长度，使得前缀的和大于等于 $0$

数据范围

• $30\%$ 的数据，$1\leq n\leq 100$
• $60\%$ 的数据，$1\leq n\leq 10,000$
• $100\%$ 的数据，$1\leq n\leq 200,000$
• $-1,0000\leq a_i\leq 1,0000$

样例数据

输入:

3
1 2 3

输出:

3

输入:

5
1 2 -1 3 -6

输出:

4