Axis

题号：NC284097
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

在一根数轴上有 $n\ (2\le n\le 10^6)$ 个点，第 $i$ 个点的坐标为 $x_i$ 。你需要给每个点分配一个非负实数 $r_i\ (r_i\ge 0)$ ，使得：

- 对于 $\forall i\in [1,n)$ ，有 $x_i+r_i\le x_{i+1}-r_{i+1}$ 。

你需要最大化 $\sum\limits_{i=1}^{n} r_i$ 的值。

第一行，输入一个数 $n$ 。
第二行，输入 $n$ 个整数，第 $i$ 个数表示第 $i$ 个点的坐标 $x_i$ 。
数据保证 $2\le n\le 10^6$ ，且 $0\le x_1\le x_2\le ...\le x_n\le 10^9$ 。

输出  的最大值。可以证明，最大值一定是一个整数。

示例1

复制

3
0 2 5

复制

示例2

复制

4
0 1 3 6

复制