1. Zábava musí byť

Pilný študent Slavo sa rozhodol dať si pauzu od každodenného kolobehu a vybral sa do zábavného parku. Zistil totiž, že tam budú mať aj jeho obľúbenú disciplínu – strieľanie zo zbraní. Slavo je už starý harcovník, čo sa (aj) strieľania týka a je teda odhodlaný vyhrať akúkoľvek súťaž, čo sa tam bude organizovať.

Keď Slavo prišiel do parku, hneď sa zastavil pri tej najväčšej tabuli široko ďaleko:

No, musíte uznať, že to¹ znie dosť dobre.

Vybral sa teda na strelnicu. Zistil, že sa strieľa z pušky a z brokovnice. S oboma už mal tú česť, takže v tom by problém nemal byť. Ba čo viac, všimol si, že vzdialenosť medzi jednotlivými terčmi je taká, že na jeden výstrel brokovnice dokáže trafiť aj dva terče vedľa seba. Už to len nedokašľať!

Terče na strelnici sú usporiadané zvláštnym spôsobom. Z pozície, odkiaľ sa strieľa, vidí strelec \(n\) terčov umiestnených v pravidelných rozostupoch vedľa seba. Za každým z týchto terčov môže (ale nemusí) byť ešte niekoľko iných terčov, akoby v zástupe. Ich počet je strelcovi dopredu známy. Z vtáčej perspektívy to celé môže vyzerať napríklad takto:

Keď sa Slavo spýtal na pravidlá, dozvedel sa nasledovné:

• Terče sú labilné, teda pri zasiahnutí terču tento (tieto) padne² a odkryje sa ďalší za ním (ak tam ešte nejaký je).

• Strelec má k dispozícii neobmedzené množstvo nábojov do oboch zbraní a môže ich ľubovoľne kombinovať a striedať.

• Cieľom hry je zhodiť všetky terče na čo najmenej výstrelov.

Ako má Slavo skombinovať pušku s brokovnicou aby potreboval čo najmenej výstrelov? Kam strieľať čím? Chce vyhrať. Musí vyhrať. Chce byť ako z Divokého Západu. Pomôžte mu!

Úloha

Pre dané počty terčov v jednotlivých zástupoch zistite, koľko výstrelov bude Slavo potrebovať, aby vyhral. Zaujíma nás teda najmenší možný počet výstrelov, na ktorý vie Slavo zasiahnuť (a zhodiť) všetky terče.

Predpokladajte, že Slavo nikdy neminie cieľ. Puškou vie trafiť ľubovoľný terč, na ktorý vidí (nezakrýva ho iný terč). Brokovnicou dokáže trafiť ľubovoľné dva terče stojace v susedných zástupoch (oba terče musí byť vidno).

Formát vstupu

V prvom riadku je jedno celé číslo \(n\) (\(1 \leq n \leq 100\,000\)) – počet radov terčov (teda počet terčov viditeľných na začiatku). Na ďalšom riadku je \(n\) medzerou oddelených kladných celých čísel \(1 \leq t_i \leq 10^9\) – \(i\)-te číslo udáva počet terčov v \(i\)-tom rade (dokopy, vrátane toho terča, ktorý vidíme).

Formát výstupu

Na výstup vypíšte jediné celé číslo – počet výstrelov, ktoré Slavo vykoná pri najlepšej možnej stratégii.

Dávajte si pozor na veľkosť čísel, s ktorými pracujete. Všimnite si, že keď budete napríklad sčítavať čísla zo vstupu, výsledok sa vám nemusí zmestiť do 32-bitovej premennej. Odporúčame preto použiť long long v C++ a Int64 v Pascale.

Príklady

Input:

3
1 6 1

Output:

6

Vstup predstavuje 3 rady terčov. V prvom a treťom rade je po jednom, v druhom rade je 6 terčov za sebou. Správna stratégia je napríklad vystreliť najprv puškou 4-krát do druhého radu a potom brokovnicou do prvých dvoch a druhých dvoch. Existujú aj iné, rovnako dobré stratégie.

Input:

5
5 1 8 5 5

Output:

18

Tento vstup zodpovedá obrázku v zadaní. Slavo strelí 8-krát puškou do stredného radu. Následne si vymení zbraň a 5-krát to brokovnicou napáli naraz na posledné dva rady. Zase si vymení zbraň, a 4-krát vystrelí na prvý rad. Nakoniec posledný krát vystrelí brokovnicou na prvý. Lepšie to nejde, no možností je opäť viac.

Input:

6
1 5 5 5 5 3

Output:

13