こっちはシージモード、あっちはドンドンドンドンドンドン！

あなたは強力な攻城戦車部隊の指揮官である。部隊は敵軍と遭遇し、攻撃の準備をしている。 敵の陣形は、$1$ から $N$ までの番号が付いた位置に一列に並んでいる。位置 $i$ の初期体力は $a_i$ である。体力が $0$ の位置には敵がいない。

戦車は、攻撃するたびに次のいずれかのモードを使用できる。

• シージモード: $1\le i\le N$ を満たす位置 $i$ を選ぶ。位置 $i$ の体力を $2$、位置 $i-1$ と の体力をそれぞれ 減らす。列の範囲外へのダメージは無視する。費用は である。

体力は負にならない。 体力 $h$ を $d$ 減らすと、$\max(0,h-d)$ になる。体力がすでに $0$ の位置を攻撃してもよい。

すべての位置の体力を $0$ にするために必要な費用の最小値を求めよ。

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

$N$ $a_1\ a_2\ \cdots\ a_N$

すべての位置の体力を $0$ にするために必要な費用の最小値を出力せよ。

• $1\le N\le 200\,000$。
• $0\le a_i\le100$ ()。