In this task you are given a long series of integers, your goal is to provide the sub of the continuous sub-series that had the maximal sum.

The definition of a continuous sub-series, is that once you are given an original series, just pick a left item and a right item (which may be the same item), the sub-series will contain all the items that are between those selected items (which are also included), in the same order as the original series.

The input is a first number N - the number of the items in the series, followed by N integers.

It is guaranteed that the sum of the sub-series is not larger than 1,000,000 and that there is at least one non-negative integer

The first example has 5 numbers, -2, 1, 2, 3, -4

The maximal sum sub-series has the sum of 1+2+3=9

The second example has 9 numbers, -1, 2, -1, 1, -1, 1, -1, 2, -1 and the largest sum is 2-1+1-1+1-1+1-1+2=3