На вершине ёлки, содержащей N веток, сидит бельчонок, который начинает прыгать по веткам вниз. Бельчонок еще маленький, и не умеет прыгать на дальние ветки, а на ближайшую ветку он не прыгает, т.к. очень стремится всем доказать, что уже большой и умеет прыгать дальше, чем на ближайшую. Поэтому он прыгает только через одну или через 2 ветки. По пути с верхушки на землю бельчонок собирает шишки, которые растут на ветках. Количество шишек на разных ветках может быть разным. В начале бельчонок сидит на самой макушке ёлки, выше верхней ветки. Последний прыжок на землю он может сделать как с 1, так и со 2 или 3 ветки, т.к. уже всем доказал, что умеет прыгать не только на ближайшую ветку. Определите:
- какое максимальное количество шишек может собрать бельчонок, спустившись с вершины ёлки на землю;
- список номеров веток, по которым проходит путь бельчонка;
- количество веток, по которым будет прыгать бельчонок
Входные данные
В первой строке записано количество веток n (2 <= n <= 1000).
Во второй строке записаны n целых чисел s
i – количество шишек на ветках (начиная с 1 ветки до n, 0 <= s
i <= 999). Нумерация веток идет снизу вверх и начинается с 1)
Выходные данные
Выведите в первой строке наибольшое количество шишек, которое может собрать бельчонок.
Во второй строке выведите через пробел номера веток, по которым он будет прыгать в порядке его следования;
В третьей строке – количество веток, по которым прыгал бельчонок
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5 10 2
|
10
2
1
|
|
2
|
7
3 1 9 5 7 6 0
|
19
5 3 1
3
|