Плата за ступени

На каждой ступени с номером от 1 до $n$ написана плата за то, чтобы на неё встать.

Кузнечик начинает с нулевой ступени, за которую платить не надо, и прыгает на одну или две ступени. Какую наименьшую сумму он заплатит, добравшись до ступени $n$?

В первой строке число $n$ от $1$ до $10^6$. Во второй — $n$ чисел от $0$ до $10^9$: плата за ступени с первой по $n$-ю.

Одно число.