"Gromozeki Checkers" - a game that is somewhat reminiscent of the Soviet board game Chapaev, named after the Civil War veteran Vasily Ivanovich Chapaev.
Rules of "Checkers Gromozeki" the following.
Rows of 5 checkers are lined up on a large chessboard. For example, 8 rows of checkers would look like this:
With each move, the player tries to knock out as many checkers as possible from the field until he knocks out all the checkers.
Gromozeka's strategy is always to hit the weakest spot. He considers a site weak, which has less than 5 checkers in a row and, at the same time, this row is limited either by the boundaries of this building, or by rows of maximum height.
The area where the most checkers are lost is considered weaker.
For example, in the position of the checkers in the figure below, there are two weak areas (rows 2 and 3; rows 7 and 8). The length of the entire building is 8. The weakest is the section of 7 and 8 rows, because 6 checkers are missing there.
Determine the row numbers that Gromozeka should aim at following his strategy. If several options are possible, print them all, starting from the leftmost row (the row with the minimum number).
Input
First enter the number N – number of rows (natural, does not exceed 1000), followed by N integers in the range from 0 to 5 – the height of the corresponding vertical row. It is guaranteed that the building has at least one weak section.
Imprint
Print, separated by a space, the number of the row from which the weakest section begins, then the number it ends with, then the number of checkers that are missing.
Examples
| # |
Input |
Output |
| 1 |
6
5 3 2 5 2 2
| 5 6 6 |
| 2 |
10
5 1 5 2 5 3 5 5 0 2
| 9 10 8 |