Задача
Робот Сильвер движется по платному шоссе на планете Шелезяка. На каждом километре шоссе расположен пункт оплаты. Всего на шоссе
n пунктов оплаты. Первый пункт оплаты находится в самом начале шоссе,
n-й пункт оплаты находится в начале последнего километра шоссе. Заплатив нужную сумму в
i-м пункте оплаты, робот может двигаться дальше либо до следующего пункта оплаты, либо же до того, который находится через 2 километра (то есть, если робот находится в пункте
i, то он может двигаться либо до пункта
i+1, либо до пункта
i+2). Первую оплату можно сделать либо в первом пункте, либо во втором (на выбор). Если оплаты была произведена в предпоследнем (
n-1) пункте, то можно просто доехать до конца шоссе, не оплачивая проезд в последнем пункте.
Зная стоимость проезда через определенный пункт оплаты, помогите роботу Сильверу найти наименьшую стоимость проезда через все шоссе, которую должен будет заплатить Сильвер, а также пункты оплаты, на которых ему необходимо будет остановиться.
Входные данные
В первой строке записано количество пунктов оплаты
n (2 <=
n <= 1000). Во второй строке записыны
n целых чисел (
costi) - стоимость проезда через
i-й пункт оплаты (1 <=
i <= n, 0 <= costi <= 999).
Выходные данные
Выведите в первой строке наименьшую стоимость проезда через шоссе.
Во второй строке выведите через пробел номера пунктов оплаты (по возрастанию), на которых роботу придется остановиться, чтобы оплатить проезд. Если вариантов маршрута с остановками в пунктах оплаты несколько, то выведите любой из них.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
10 15 20 |
15
2 |
| 2 |
10
1 100 1 1 1 100 1 1 100 1 |
6
1 3 5 7 8 10 |