Joe and Bob are bus drivers, both working for the same company and driving the same route. Joe and Bob's bus route can be modeled as a line of $N$ bus stops, with $p_i$ passengers waiting to board at each stop $i$ for $1\le i\le N$. Since each of their buses travels at very high speeds (very dangerous driving, that's for sure), the distance between stops can be considered to be negligible. Joe and Bob will each leave from the initial station (before stop $1$) and eventually arrive at the last station (past stop $N$). Whenever one of them arrives at a stop, they must allow each person waiting at that stop to board their bus, taking $1$ second for each passenger.

If both Joe and Bob arrive at a stop at the same time, Bob will pick up the passengers (because Joe is a meanie). Furthermore, only one driver can pick up passengers from a stop at a time: if the other driver reaches that stop, they simply go past.

Joe is competitive and wants to beat Bob to the last station by the greatest amount of time possible. Joe, being devious, has decided that if necessary he will stop for an arbitrary number of seconds between stops in order to allow Bob to pick up passengers at the next stop. Joe wishes to know the maximum time by which he can beat Bob; that is, the largest possible number of seconds between their arrivals at the last station.

Constraints

$1\le N\le {10}^5$

$1\le p_i\le {10}^9$

Input Specification

The first line of input will contain a single integer $N$, the number of bus stops on the route. The second line of input will contain $N$ space separated integers, the number of passengers waiting at each bus stop.

Output Specification

Output on a single line the greatest number of seconds by which Joe can beat Bob, or $-1$ if Bob will always arrive earlier than Joe.

Sample Input

9
5 3 9 6 1 3 8 1 3

Sample Output

4