«Шашки Громозеки» - игра, напоминающая чем-то советскую настольную игру Чапаев, получившая название по фамилии участника Гражданской войны Василия Ивановича Чапаева.
Правила «Шашек Громозеки» следующие.
На большой шахматной доске выстраиваются ряды шашек по 5 штук. Например, 8 рядов шашек будут выглядеть следующим образом:
Каждым ходом игрок пытается выбить как можно больше шашек с поля, пока не выбьет все шашки.
Стратегия Громозеки заключается всегда в том, чтобы бить по самому слабому участку. Слабым он считает участок, у которого в ряду менее 5 шашек и, при этом, данный ряд ограничен либо границами данной постройки, либо же рядами максимальной высоты.
Более слабым считается тот участок, в котором потеряно больше всего шашек.
Например, в положении шашек на рисунке ниже, есть два слабых участка (ряды 2 и 3; ряды 7 и 8). Длина всей постройки равна 8. Наиболее слабым является участок 7 и 8 рядов, потому что там отсутствует 6 шашек.
Определите номера рядов, в которые должен целиться Громозека, следуя своей стратегии. Если возможны несколько вариантов, выведите их все, начиная с самого левого ряда (ряда с минимальным номером).
Входные данные
Сначала вводится число N – количество рядов (натуральное, не превышает 1000), затем следует N целых чисел в диапазоне от 0 до 5 – высота соответствующего вертикального ряда. Гарантируется, что в постройке есть хотя бы один слабый участок.
Выходные данные
Выведите через пробел номер ряда, с которого начинается самый слабый участок, затем номер, которым он заканчивается, затем количество шашек, которые отсутствуют.
Примеры
| № |
Входные данные |
Выходные данные |
| 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 |