Группа туристов спускается с вершины горы. На их пути встречаются кордоны, расположенные на каждой версте пути. Чтобы пройти кордон, нужно либо оплатить пошлину, либо предъявить купон об оплате пошлины на другом, соседнем, кордоне. Соседними считаются кордоны, находящиеся на расстоянии не более трех верст. Однако, на вершине последние две версты считаются самыми сложными, и караул этих кордонов всегда лояльно относится к тем стойким утристам, которые смогли дойти до них, и плату не требует. Таким образом, в начале пути пройти без оплаты туристы смогут не более двух последних кордонов, а в конце - не более двух первых. Величина пошлины на разных кордонах может быть различной. Помогите туристам минимизировать затраты на пошлину.
Зная величину пошлины на каждом из кордонов, определите:
- какую минимально возможную суммарную пошлину туристы заплатят
- список порядковых номеров кордонов, в которых нужно производить оплату, чтобы минимизировать затраты; в порядке их прохождения;
- количество остановок туристов на кордонах для оплаты пошлины.
.
Входные данные
В первой строке записано количество кордонов n (1 <= n <= 10000). Во второй строке записаны n целых чисел s
i - пошлина, взимаемая на i-ом кордоне (0 <= s
i <= 999).
Выходные данные
Выведите в первой строке наименьшие суммарные затраты на пошлину.
Во второй строке выведите через пробел номера кордонов, на которых нужно оплатить пошлину, в порядке их прохождения. Нумерация кордонов начинается с 1, с самого нижнего. Если вариантов маршрута с остановками несколько, то выведите любой из них.
В третьей строке выведите общее количество кордонов, на которых туристы будут оплачивать пошлину.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5 10 2
|
2
3
1
|
|
2
|
7
3 1 9 5 7 6 0
|
6
7 4 2
3
|