ZQFMGB12 often loans money to other people. As a result, many people are in debt to him. Initially, on day ~0~, his friends collectively owe him $0. Over ~N~ days, numbered from ~1~ to ~N~, one of his friends can either borrow money or return money that is owed to ZQFMGB12. It is possible that his friends return so much money such that he owes his friends back money (i.e. his friends owe him a negative amount).
After the ~N~ days of borrowing/returning, ZQFMGB12 acquires a time machine and would like to go back to the day where his friends have the most total debt. If there are multiple days where his friends have the most total debt, he wants to go the earliest one of them. Please determine which day this is!
The first line of input will contain an integer ~N~ ~(1 \leq N \leq 100\,000)~, the number of days.
~N~ lines of input follow. The line can either be
borrow x, signifying that ~x~ dollars are borrowed from ZQFMGB12 (increase in debt), or
return x, signifying that ~x~ dollars has been returned to him (decrease in debt). ~x~ is guaranteed to be non-negative, and the absolute value of the total debt at any time will not exceed ~10^9~.
Output a single integer from ~0~ to ~N~ that signifies the earliest day where ZQFMGB12's friends owe him the most.
5 borrow 38 borrow 10 return 5 borrow 5 return 20
Explanation For Sample Output
On days 2 and 4, ZQFMGB12's friends owe him $48, the highest debt. He would want to go back to day 2 over day 4 since it is earlier.