Recycling

문제

Heck S. Quincy (or Hex as his friends call him) is in charge of recycling efforts in the Quad Cities within the greater Tri-state area as well as the Twin Cities in the Lone Star State.  One of the programs he oversees is the placement of large recycling bins at various locations in the cities.  Transporting these bins is very expensive so he tries to keep them at any given location for as long as possible, emptying them once a week. He's willing to keep a bin at a given location as long as it is full at the end of each week.

Hex has very reliable estimates of the amount of recyclable materials (in cubic meters) that he can expect each week at each location.  Given this information he would like to know when to install the recycling bin of an appropriate size to maximize the amount of material recycled. He will keep the bin at that location up to (but not including) the week when they don't expect it to be filled to capacity.

For example, suppose Hex has the following estimates for the next seven weeks: $257351022\backslash \; 5\backslash \; 7\backslash \; 3\backslash \; 5\backslash \; 10\backslash \; 2$. Hex has several options for placing bins, including:

• A capacity-$22$ bin from week $11$ until week $77$, recycling $14{\text{m}}^{3}14\backslash textrm\{m\}^3$
• A capacity-$55$ bin from week $22$ until week $33$, recycling $10{\text{m}}^{3}10\backslash textrm\{m\}^3$
• A capacity-$33$ bin from week $22$ until week $66$, recycling $15{\text{m}}^{3}15\backslash textrm\{m\}^3$ (this is the maximum possible)

Hex would not place a capacity-$55$ bin from week $22$ until week $66$, since it would not be filled in week $44$.

입력

Input starts with a line containing a single positive integer $nn$ ($n\le 100000n\; \backslash leq\; 100\backslash ,000$) indicating the number of weeks which Hex has estimates for. Weeks are numbered $11$ to $nn$.  Following this are $nn$ non-negative integers listing, in order, the amount of recycling expected for each of the $nn$ weeks. These values may be over multiple lines.

출력

Output three integers $ss$ $ee$ $rr$ where $ss$ and $ee$ are the start and end weeks for when to place the bin to maximize the total recycling and $rr$ is that maximum amount. If there are two or more time periods that lead to the same maximum amount, output the one with the smallest $ss$ value.

힌트

Ambiguous Test Case

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

• 1 50000 2500050000
• 1 50001 2500050000

• Input
• Judges' answer

7
2 5 7 3 5
10 2

2 6 15

8
2 5 7 3 5
10 2 4

1 8 16