Робот Сильвер движется по платному шоссе на планете Шелезяка. На каждом километре шоссе расположен пункт оплаты. Всего на шоссе
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
|
10
1 100 1 1 1 100 1 1 100 1
|
6
|