В ЛП-ляндии король поручил шпиону Битику узнать, какие инновации есть в соседней ДП-ляндии. Как известно, лучше всего новости узнаются в придорожных трактирах. Дорога в ДП-ляндии одна, и все трактиры расположены вдоль нее. Однако за посещение трактира нужно платить. Король выделил Битику на посещение трактиров ДП-ляндии внушительную сумму. Но Битик, чтобы сэкономить, решил посещать не все трактиры. Он полагет, что в трактирах, расположенных рядом, новости пересекаются, поэтому он может пропустить один или два трактира. Однако хотя бы в каждом третьем трактире Битику надо побывать, чтобы не пропустить что-то важное. Строго говоря, Битик может пропустить не более двух подряд расположенных трактиров, причем хотя бы один трактир он в любом случае должен посетить. Но, т.к. в разных трактирах оплата может различаться, Битик запутался, какие именно трактиры ему следует посетить, а какие можно пропустить. Помогите ему минимизировать расходы на оплату трактиров.
Зная стоимость посещения для каждого трактира, определите:
- сколько денег потратит Битик на трактиры;
- список порядковых номеров трактиров, которые нукжно посетить, в порядке возрастания;
- количество остановок Битика.
.
Входные данные
В первой строке записано количество придорожных трактиров n (1 <= n <= 10000). Во второй строке записаны n целых чисел s
i - стоимость посещения i-го трактира (0 <= s
i <= 999).
Выходные данные
Выведите в первой строке наименьшие суммарные затраты Битика.
Во второй строке выведите через пробел номера трактиров (по возрастанию), которые Битику нужно посетить. Нумерация начинается с 1. Если вариантов маршрута с остановками несколько, то выведите любой из них.
В третьей строке выведите общее количество трактиров, которые нужно посетить Битику .
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
23 25 12 10
|
12
3
1
|