该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

在一维数轴上，有 $n$ 个水果，它们分别位于坐标 $p_i$（保证 $p_i \le p_{i+1}$）。现在，orange要为所有水果分配领地，分配规则应该满足：

• 若第 $i$ 位水果得到的领地半径位 $r_i$，则其领地范围为 $[p_i-r_i, p_i+r_i]$。
• 你需要保证所有水果的领地不重叠（只能相切），即 $\forall p_i + r_i \le p_{i+1}-r_{i+1}$。

你需要求出每个水果能分到的领地半径之和 $\sum r_i$ 的最大值是多少。

Format

Input

第一行，输入一个数 $n$。

第二行，输入一个长度为 $n$ 的序列 $p_i$。

数据范围

$2 \le n \le 10^6$

$0 \le p_i \le p_{i + 1} \le 10^9$

Output

一个整数表示答案。

Samples

3
0 2 5

5

4
0 1 3 6

4