D - Ears 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 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

出力

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

入力例 1

4
1
0
2
3

出力例 1

1

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

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

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

入力例 2

8
2
0
0
2
1
3
4
1

出力例 2

3

入力例 3

7
314159265
358979323
846264338
327950288
419716939
937510582
0

出力例 3

1

Score : 600 points

Problem Statement

Snuke stands on a number line. He has L ears, and he will walk along the line continuously under the following conditions:

  • He never visits a point with coordinate less than 0, or a point with coordinate greater than L.
  • He starts walking at a point with integer coordinate, and also finishes walking at a point with integer coordinate.
  • He only changes direction at a point with integer coordinate.

Each time when Snuke passes a point with coordinate i-0.5, where i is an integer, he put a stone in his i-th ear.

After Snuke finishes walking, Ringo will repeat the following operations in some order so that, for each i, Snuke's i-th ear contains A_i stones:

  • Put a stone in one of Snuke's ears.
  • Remove a stone from one of Snuke's ears.

Find the minimum number of operations required when Ringo can freely decide how Snuke walks.

Constraints

  • 1 \leq L \leq 2\times 10^5
  • 0 \leq A_i \leq 10^9(1\leq i\leq L)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

L
A_1
:
A_L

Output

Print the minimum number of operations required when Ringo can freely decide how Snuke walks.

Sample Input 1

4
1
0
2
3

Sample Output 1

1

Assume that Snuke walks as follows:

  • He starts walking at coordinate 3 and finishes walking at coordinate 4, visiting coordinates 3,4,3,2,3,4 in this order.

Then, Snuke's four ears will contain 0,0,2,3 stones, respectively. Ringo can satisfy the requirement by putting one stone in the first ear.

Sample Input 2

8
2
0
0
2
1
3
4
1

Sample Output 2

3

Sample Input 3

7
314159265
358979323
846264338
327950288
419716939
937510582
0

Sample Output 3

1