AT_yahoo_procon2019_qual_d Ears

[problemUrl]: https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d 数直線上にすぬけ君がいます。すぬけ君は $ L $ 個の耳を持っており、以下の条件を満たしながら数直線上を連続的に散歩します。 - 座標 $ 0 $ 未満の点や座標が $ L $ より大きい点を通ることはない - 整数座標の点で散歩を開始し、整数座標の点で散歩を終了する - 整数座標の点でのみ、進む方向を変えることができる すぬけ君は、座標が整数 $ i $ を用いて $ i-0.5 $ と表される点を通るたびに、$ i $ 番目の耳に石を $ 1 $ 個入れます。 すぬけ君が散歩を終えた後、りんごさんは以下の操作を好きな順に何度でも繰り返すことで、 各 $ i $ に対しすぬけ君の $ i $ 番目の耳には $ A_i $ 個の石が入っているようにしたいです。 - すぬけ君の耳をひとつ選び、石を $ 1 $ 個入れる - 石が $ 1 $ 個以上入っているすぬけ君の耳をひとつ選び、石を $ 1 $ 個取り出す すぬけ君の散歩の方法をりんごさんが好きに決められるとき、必要な操作の回数の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ L $ $ A_1 $ $ : $ $ A_L $

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

### 制約 - $ 1\ \leq\ L\ \leq\ 2\times\ 10^5 $ - $ 0\ \leq\ A_i\ \leq\ 10^9(1\leq\ i\leq\ L) $ - 入力はすべて整数である ### Sample Explanation 1 すぬけ君が以下のように散歩をするとします。 - 座標 $ 3 $ から散歩を開始し、座標 $ 4 $ で終了する。座標 $ 3,4,3,2,3,4 $ と順に訪れる。 このとき、すぬけ君の耳には順に $ 0,0,2,3 $ 個の石が入っています。 りんごさんがすぬけ君の $ 1 $ 個目の耳に $ 1 $ 個の石を入れることで、条件を満たすことができます。