说明

给定 n 个整数 a1,a2,..,an，请问这个序列最长有多少长的前缀，满足元素的和大于或等于0?如果任何长度大于 0 的前缀之和都为负数，则输出 0

输入格式

第一行:单个整数表示 n
第二行:n 个整数表示 a1,a2,...,an

输出格式

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

样例

3
1 2 3

3

提示

数据范围：

    30% 的数据，1 ≤ n ≤ 100
    60% 的数据，1 ≤ n  ≤ 10,000
    100% 的数据，1 ≤ n ≤ 200,000
    -1,0000  ≤ ai  ≤ 1,0000