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