时间限制： 1.0 秒

空间限制： 512 MB

题目描述

Bob 喜欢一维坐标，现在，在一根数轴上有 $2\ (2\le n\le 10^6)$ 个点，第 $i$ 个点的坐标为 $x_i$。

他想要给每个点分配一个非负实数 $r_i\ (r_i\ge 0)$，可以理解为以第 $i$ 个点为中心的“半径”。这些半径需要满足：

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

Bob 希望最大化 $\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 \cdots \le x_n\le 10^9$。

输出格式

输出到标准输出。

输出 $\sum\limits_{i=1}^n r_i$ 的最大值。可以证明，最大值一定是一个整数。

3
0 2 5

5

4
0 1 3 6

4

子任务

对于所有数据，保证 $2\le n\le 10^6$，且 $0\le x_1\le x_2\le \cdots x_n\le 10^9$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。