Shoot 'Em Down

Background

„Am rătăcit în labirint douăzeci de minute înainte de a intra în sfârșit în sala mare. Pereții erau acoperiți de oglinzi și aici, sub tavan atârnau balcoane mici unde stăteau monștri. Nu mai văzusem niciodată așa ceva. Aveau ochi mari, bombați, tentacule lungi care țineau ferm shotgun-uri și corpuri solzoase, asemănătoare oamenilor–pește. Monștrii au tras în mine de pe balcoane, iar eu am tras înapoi folosind Chu Ko Nu-ul meu. Împuşcătura a spulberat trei oglinzi umplând camera cu un fum argintiu. Gloanțele mi-au lovit armura, doborându-mă la podea. Căzând, am reușit să trag o săgeată și m-am ridicat la fel de repede cum am căzut, rotindu-mă pe spate, așa cum făceam în tinerețe în timp ce făceam break dance, toate acestea în timp ce trăgeam încă de trei ori. Trei oglinzi, trei oglinzi, trei oglinzi...”
- Citat de Sergey Lukjanenko, „The Labyrinth of Reflections”

Enunț

Chu Ko Nu distruge trei balcoane adiacente dintr-un foc. (Al $N$-lea balcon este adiacent primului). După tragere, monștrii care supraviețuiesc îi provoacă daune lui Leonid (eroul principal al romanului) — o unitate per monstru. Urmează o nouă tragere și așa mai departe până când toți monștrii vor pieri. Este necesar să se definească cantitatea minimă de daune, pe care o poate primi Leonid.

Date de intrare

Prima linie conține numărul întreg $N$, numărul de balcoane, pe care monștrii au luat o apărare circulară. A doua linie conține $N$ numere întregi, numărul de monștri pe fiecare balcon.

Date de ieșire

Afișați numărul minim de daune cu care Leonid poate scăpa după ce omoară toți monștrii.

Restricții și precizări

• $3 \leq N \leq 20$;
• $1 \leq$ numărul de monștrii din fiecare balcon $\leq 1\ 000$;
• Primul balcon este adiacent cu ultimul;
• Dacă alegeți să eliminați monștrii din 3 balcoane adiacente iar unul sau două dintre acele balcoane nu mai conțin monștrii, evident că se vor elimina doar monștrii din balconul/balcoanele în care se află aceștia.

Exemplu

stdin

7
3 4 2 2 1 4 1

stdout

9

Explicație

Soluția optimă este de a elimina monștrii din primele 3 balcoane, ceea ce înseamnă că monștrii din restul balcoanelor vor trage în Leonid, adică $2+1+4+1 = 8$, iar apoi se vor elimina următoarele 3 balcoane ceea ce înseamnă că va primi daună doar din ultimul balcon ceea ce înseamnă că se va adăuga $1$ la daunele totale, urmând ca la pasul următor să fie eliminat ultimul balcon, ceea ce ne lasă cu o daună totală egală cu $9$.