Metropolis to Beach

You are one of the organisers of this year's largest running race, the Metropolis to Beach™. This race starts in the city of Metropolis and finishes at the beach. The race route spans $N$ city blocks, each of which is either flat, or runs uphill or downhill. Because the organisers would like this to remain a fun event open to as many runners as possible, there is a strict limit on the maximum elevation increase of any fully uphill section. A fully uphill section is a consecutive series of city blocks, which are all uphill (flat sections don't count). Given the race route, what is the maximum elevation change of any uphill section?

Input

The first line contains a single integer, $N$ ($2 \le N \le 100000$).

The next $N$ lines contain the elevation changes of the city blocks in the race, in order. In other words, if the city block is flat, the elevation change is $0$, if it is uphill, the elevation change is positive, and if it is downhill, the elevation change is negative. The elevation change of any section will not be greater than 1000 (either uphill or downhill).

Output

Print a single integer - the maximum elevation change of any fully uphill section. If there are no fully uphill sections, print $-1$.

Subtasks

• For 30% of the marks, each block is uphill.
• For an additional 30% of the marks, $2 \le N \le 100$.