Applejack is a female Earth pony. She lives and works at Sweet Apple Acres with her grandmother Granny Smith, her older brother Big McIntosh, her younger sister Apple Bloom, and her dog Winona. She represents the element of honesty.
Now Applejack is going to cultivate a row of wasteland, and it could be transformed into the following model:
There are $$$n$$$ cells in a row, each containing an integer $$$a_i$$$. Applejack start by cultivating cell number $$$1$$$ and have $$$0$$$ resources just before the end of time unit 1.
Later, assuming Applejack have cultivated cells $$$[1, x]$$$, at the beginning of each unit time, she can cultivate cell $$$x+1$$$, and at the end of each unit time, she obtain resources equal to the sum of integers on all cells she have cultivated.
Applejack need to ensure that she always have non-negative resources(even after cultivating all cells). What is the minimum time needed to occupy all cells, or is it impossible?
The first line contains an integer $$$n$$$ $$$(2\le n\le 10^5)$$$ which represents the length of the row of cells.
The second line contains $$$n$$$ integers $$$a_i$$$ $$$(-10^8\le a_i\le 10^8)$$$, representing the coefficients on the cells.
Output a single integer representing the minimum amount of time needed to occupy all cells, if a solution exists.
Otherwise, output $$$-1$$$.
3 1 -3 4
4
3 1 -4 2
-1
6 1 -2 1 -4 5 -1
10
In the first example, Applejack can stay cell $$$1$$$ until time $$$3$$$, then she can cultivate cell $$$2$$$ and cell $$$3$$$ at time $$$3$$$ and time $$$4$$$.
And at the end of time $$$1$$$, time $$$2$$$, time $$$3$$$, time $$$4$$$, she have $$$1, 2, 0, 2$$$ resource correspondingly.
In the second example, after cultivating all cells, the resources will eventually be negative.
