Робот Сильвер едет по шоссе. Вдоль дороги стоят n пунктов оплаты — по одному на каждый километр. На пункте
i написана плата
cost[i]: столько робот отдаёт, если останавливается у этого пункта. Пункт, мимо которого он проехал не останавливаясь, не оплачивается.
Перед шоссе есть бесплатный въезд, а после — бесплатный съезд. Робот стартует со въезда, едет только вперёд, и от каждой остановки до следующей проезжает 1 или 2 пункта. Доехать ему надо до съезда.
Найдите наименьшую сумму, которую заплатит робот.
Формат входных дынных
В первой строке записано количество пунктов оплаты
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
|