配点 : $600$ 点

問題文

数直線上にすぬけ君がいます。すぬけ君は $L$ 個の耳を持っており、以下の条件を満たしながら数直線上を連続的に散歩します。

• 座標 $0$ 未満の点や座標が $L$ より大きい点を通ることはない
• 整数座標の点で散歩を開始し、整数座標の点で散歩を終了する
• 整数座標の点でのみ、進む方向を変えることができる

すぬけ君は、座標が整数 $i$ を用いて $i-0.5$ と表される点を通るたびに、$i$ 番目の耳に石を $1$ 個入れます。

すぬけ君が散歩を終えた後、りんごさんは以下の操作を好きな順に何度でも繰り返すことで、 各 $i$ に対しすぬけ君の $i$ 番目の耳には $A_i$ 個の石が入っているようにしたいです。

• すぬけ君の耳をひとつ選び、石を $1$ 個入れる
• 石が $1$ 個以上入っているすぬけ君の耳をひとつ選び、石を $1$ 個取り出す

すぬけ君の散歩の方法をりんごさんが好きに決められるとき、必要な操作の回数の最小値を求めてください。

制約

• $1 \leq L \leq 2\times 10^5$
• $0 \leq A_i \leq 10^9(1\leq i\leq L)$
• 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

$L$

$A_1$

$:$

$A_L$

出力

必要な操作の回数の最小値を出力せよ。

4
1
0
2
3

1

すぬけ君が以下のように散歩をするとします。

• 座標 $3$ から散歩を開始し、座標 $4$ で終了する。座標 $3,4,3,2,3,4$ と順に訪れる。

このとき、すぬけ君の耳には順に $0,0,2,3$ 個の石が入っています。 りんごさんがすぬけ君の $1$ 個目の耳に $1$ 個の石を入れることで、条件を満たすことができます。

8
2
0
0
2
1
3
4
1

3

7
314159265
358979323
846264338
327950288
419716939
937510582
0

1