A small business logs its net daily cash change (a gain or a loss) for n days, starting from a balance of exactly 0 before day 1. Given the n daily changes, find the first day (1-indexed) on which the cumulative balance becomes strictly negative.
If the cumulative balance never goes below zero, print -1 instead.
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the net change for day 1, day 2, ..., day n.
Output format
A single integer: the 1-indexed day on which the cumulative balance first goes strictly below zero, or -1 if that never happens.
Constraints
- 1 <= n <= 100000
- -1000000 <= change <= 1000000