Find First Index Where Prefix Sum Becomes Non-Positive

Find the earliest non-empty prefix whose sum is ≤0; if there is none, output −1. This site's standard I/O explicitly uses 0-based indices: the source's examples 2 and 3 mix index conventions, so the result of example 2 is corrected from 2 to 1.

输入格式

The first line contains n (1..100000), and the second line contains n integers in −10^9..10^9.

输出格式

Output a single integer answer.

样例 1

输入：

2
1 2

输出：

-1

样例 2

输入：

3
2 -4 1

输出：

1

样例 3

输入：

4
1 2 3 -6

输出：

3

样例说明

Example 1: the prefixes 1 and 3 are both positive, so output −1. Example 2: the prefixes are 2, −2, −1, and the first one occurs at index 1. Example 3: the prefixes are 1, 3, 6, 0, and the first one is at index 3.