В сказочном королевстве жил-был портной. Однажды он решил навестить своего друга сапожника, проживающего в другом городе. Путь был не близкий и портному требовалась остановка на ночлег в придорожных гостиницах. Денег у него было немного. Помогите портному минимизировать расходы на оплату своего путешествия. Известно, что портной мог останавливаться в каждой придорожной гостинице, а мог пропускать одну или две гостиницы. Первую остановку портной может сделать либо в первой встретившейся гостинице, либо во второй, либо в третьей (на выбор).
Зная стоимость проживания за 1 сутки в каждой гостинице, определите:
- сколько денег потратил портной на свое путешествие;
- список порядковых номеров гостиниц, в которых он останавливался на ночлег в порядке возрастания;
- количество остановок портного.
Известно, что стоимость проживания во всех гостиницах разная.
Входные данные
В первой строке записано количество придорожных гостиниц n (0 <= n <= 1000). Во второй строке записаны n целых чисел si - стоимость проживания в i-й гостинице за сутки (0 <= i <= n, 0 <= si <= 999).
Выходные данные
Выведите в первой строке наименьшую стоимость путешествия портного.
Во второй строке выведите через пробел номера гостиниц (по возрастанию), в которых портному придется останавливаться, чтобы переночевать. Если вариантов маршрута с остановками в гостиницах несколько, то выведите любой из них.
В третьей строке выведите количество гостиниц, в которых останавливался портной.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
10
|
0
0
0
|
|
2
|
3
15 12 23
|
12
2
1
|