Problem description

Małpka Bajtozja spaceruje po linie w cyrku. Lina jest podzielona na N kawałków jednostkowych. Małpka jest w stanie wykonać krok o jeden lub o dwa kawałki jednostkowe do przodu. Niestety, niektóre miejsca liny są niebezpieczne – dla każdego kawałka jednostkowego małpka określiła jego współczynnik niebezpieczeństwa. Małpka chce przejść przez linę przy zminimalizowaniu sumarycznego współczynnika.

Małpka startuje zaraz przed pierwszym kawałkiem jednostkowym (w pierwszym kroku może przeskoczyć albo na pierwszy albo na drugi kawałek jednostkowy), a kończy zaraz za ostatnim kawałkiem jednostkowym (w ostatnim kroku może przeskoczyć albo z ostatniego albo z przedostatniego kawałka jednostkowego).

Napisz program, który: wczyta opis liny, wyznaczy minimalny sumaryczny współczynnik niebezpieczeństwa przejścia liny i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca liczbę kawałków jednostkowych, na które podzielona jest lina. W drugim (ostatnim) wierszu wejścia znajduje się ciąg N liczb całkowitych pooddzielanych pojedynczymi odstępami – i-ta liczba określa współczynnik niebezpieczeństwa i-tego kawałka jednostkowego liny.

Wyjście

W pierwszym (i jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita – minimalny sumaryczny współczynnik niebezpieczeństwa dla optymalnej trasy Bajtozji.

Ograniczenia

1 ≤ N ≤ 1 000 000, 0 ≤ A_i ≤ 10⁹.

Przykład

6
3 0 1 5 2 1

3