ペペロの処分

$N$人が一列に並んでいる。左から$i$番目の人は、最初にペペロを$A_i$本持ち、左または右を向いている。1番目の人の左と$N$番目の人の右には、それぞれごみ箱がある。

次の操作を繰り返すことができる。

1. ペペロを1本以上持っている人を1人選ぶ。
2. 選んだ人は、向いている方向の隣の人にペペロを1本渡す。その方向に隣の人がいなければ、ごみ箱に入れる。
3. 選んだ人は、向いている方向を反転する。

ごみ箱に入ったペペロは取り出せない。人を選ぶ順番は自由に決められる。すべてのペペロを捨てるために必要な操作回数の最小値を求めよ。

入力は次の形式で与えられる。

$N$ $A_1\ A_2\ \cdots\ A_N$

すべてのペペロを捨てるために必要な操作回数の最小値を出力せよ。

• $1 \leq N \leq 200\ 000$.
• $0 \leq A_i \leq 10^8$ ().