题目描述

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

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

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

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

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

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

输入格式

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

$L$ $A_1$ $:$ $A_L$

输出格式

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

题目大意

题目描述

在一个数轴上，有 $L$ 堆石头，第 $i$ 堆石头的坐标是 $i-0.5$。 刚开始石头堆数为 $0$。

• 你可以从任何地方出发，在任何地方结束移动。（坐标为整数）

• 你每次只能向左或右移动 $1$。

• 你在经过一堆石头时会向其添加一块石头。

• 若坐标为 $x$，那么你必须保证 $0 \leq x \leq L$。

给定 $L,A_1,A_2,A_3,\cdots,A_L$，假设最后第 $i$ 堆石头数量为 $H_i$，求 ：

$$\min(\sum_{i=1}^{L} |A_i-H_i| )$$

---

输入格式

$L+1$ 行，为

$L\\A_1\\A_2\\A_3\\\cdots\\A_L$

---

输出格式

一行一个整数，

$$\min(\sum_{i=1}^{L} |A_i-H_i| )$$

---

数据范围

• $1 \leqslant L \leqslant 2\times 10^5$

• $0 \leqslant A_i \leqslant 10^9(1 \leqslant i \leqslant L)$

• 输入均为整数

---

$\textsf{Translate by @\color{5EB95E}nr0728}.$

4
1
0
2
3

1

8
2
0
0
2
1
3
4
1

3

7
314159265
358979323
846264338
327950288
419716939
937510582
0

1

提示

制約

• $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$ 個の石を入れることで、条件を満たすことができます。