C - 一次元オセロ Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

りんごさんは一次元オセロで遊んでいます。一次元オセロとは、無限に長い 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 < 10^5, N は奇数) が与えられる。
  • 2 行目には、コマの初期配置の情報を表す N 個の整数が空白区切りで与えられる。このうち i (1 ≦ i ≦ N) 番目には A_i (1 ≦ A_i ≦ 10^8) が与えられる。

出力

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

入力例1

5
1 2 3 4 5

出力例1

20

下図のようにコマを置いていくと、全部で 1+4+5+10 = 20 回コマをひっくり返すことになります。

figure1

入力例2

9
100000000 20 15 11 14 20 15 11 15

出力例2

554