AT_cf_2015_morning_hard_a 一次元オセロ

[problemUrl]: https://atcoder.jp/contests/code-festival-2015-morning-middle/tasks/cf_2015_morning_hard_a りんごさんは一次元オセロで遊んでいます。一次元オセロとは、無限に長い $ 1 $ 列に並んだマス目と、特殊なコマを使って遊ぶゲームです。一次元オセロで用いるコマは表が黒色で裏が白色のコマで、黒のコマを裏返すと白のコマに、白のコマを裏返すと黒のコマになります。一次元オセロは以下のように進行します。 1. まず、白のコマ $ A_1 $ 個、黒のコマ $ A_2 $ 個、白のコマ $ A_3 $ 個、...、白のコマ $ A_N $ 個をこの順に連続したマス目に置く。 2. 黒のコマをいずれかの空きマスに置く。このとき、隣の $ 2 $ マスのうちちょうど $ 1 $ マスに白のコマがなければならない。 3. $ 2. $ で置いた黒のコマに最も近い別の黒のコマ（そのようなコマは常に一意に定まる）との間にある白のコマを全て裏返して黒のコマにする。 4. $ 2. $ と $ 3. $ の黒と白を入れ替えた操作を行う。 5. $ 2. $ 〜 $ 4. $ を繰り返す。 6. $ 3. $ または $ 4. $ を終えた時点で、全てのコマが同じ色になった場合はその時点で終了となる。 たくさんのコマを裏返すのは大変なので、りんごさんはコマを裏返す回数を少なくしたいと思っています。ゲームが終了するまでにりんごさんが裏返すコマの個数の和の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ ... $ A_N $ - $ 1 $ 行目には、整数 $ N\ (3\ ≦\ N\

ゲームが終了するまでにりんごさんが裏返すコマの個数の和の最小値を $ 1 $ 行に出力せよ。出力の末尾に改行を入れること。

### Sample Explanation 1 下図のようにコマを置いていくと、全部で $ 1+4+5+10\ =\ 20 $ 回コマをひっくり返すことになります。 !\[figure1\](https://code-festival-2015-morning-hard.contest.atcoder.jp/img/other/code\_festival\_2015\_final/asa/osero.png)