Recycling

Heck S. Quincy (friends call him Hex) oversees recycling in the Quad Cities of the greater Tri-state area and the Twin Cities in the Lone Star State. One of his programs places large recycling bins at various locations in the cities. Transporting a bin is expensive, so he keeps each bin at its location for as long as possible and empties it once a week. He keeps a bin at a location as long as it is full at the end of each week.

Hex has reliable estimates of the recyclable material (in cubic meters) he can expect each week at each location. Given these estimates, he wants to know when to install a bin of the right size to maximize the amount recycled. He keeps the bin at that location up to, but not including, the first week when the bin is not expected to fill to capacity.

For example, suppose the estimates for the next seven weeks are $2\ 5\ 7\ 3\ 5\ 10\ 2$. Hex has several options, including:

• A capacity-2 bin from week 1 to week 7, recycling $14\textrm{m}^3$
• A capacity-5 bin from week 2 to week 3, recycling $10\textrm{m}^3$
• A capacity-3 bin from week 2 to week 6, recycling $15\textrm{m}^3$ (the maximum possible)

Hex would not place a capacity-5 bin from week 2 to week 6, since it would not be filled in week 4.

The first line contains a single positive integer $n$ ($n \leq 100\,000$), the number of weeks with estimates. Weeks are numbered 1 to $n$. The next $n$ values are non-negative integers giving the expected amount of recycling for each week, in order. These values may span multiple lines.

Output three integers $s$ $e$ $r$, where $s$ and $e$ are the start and end weeks for placing the bin, and $r$ is the maximum total amount recycled. If two or more periods reach the same maximum, output the one with the smallest $s$.

There is one ambiguous test case. It is not included in the zip file. The two possible answers are:

• 1 50000 2500050000
• 1 50001 2500050000