Плата и два прыжка

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

В первой строке число $n$ от $1$ до $10^6$. Во второй — $n$ чисел от $0$ до $10^9$.

Одно число.