题目描述

有 $N$ 个人站在数轴上，分别记为 Person $1$ 到 Person $N$。Person $i$ 现在位于数轴上的坐标 $A_i$ 处。
其中，$A_1 < A_2 < A_3 < \dots < A_N$，且所有 $A_i$ 都是偶数。

我们将在 $k$ 秒内举办一个派对。
在派对期间，每个人可以自由地在数轴上以最多 $1$ 的速度移动。（也允许在速度限制内向负方向移动。）
人们要求满足以下条件：对于每个 $i$（$1 \le i \lt N$），派对期间至少有一个时刻（包括结束时刻），Person $i$ 和 Person $i+1$ 在同一坐标处。

找到满足所有条件的一种策略所需的最小 $k$。
我们可以证明，在该问题的约束条件下，答案是一个整数。

约束条件

• $2 \le N \le 2 \times 10^5$
• $0 \le A_i \le 10^9$
• $A_1 < A_2 < A_3 < \dots < A_N$
• $A_i$ 是偶数。

输入

输入从标准输入中按以下格式给出：

$N$ $A_1$ $A_2$ $A_3$ $\dots$ $A_N$

输出

以整数形式输出答案。

示例输入 1

3
0 6 10

示例输出 1

5

在持续 $5$ 秒的派对中，每个人应按照以下方式移动：

• Person $1$: 总是以速度 $1$ 向正方向移动。
• Person $2$: 前 $2$ 秒内以速度 $1$ 向正方向移动，之后的 $3$ 秒内以速度 $1$ 向负方向移动。
• Person $3$: 总是以速度 $1$ 向负方向移动。

如果按照这种方式移动，Person $2$ 和 Person $3$ 将在开始后的 $2$ 秒内位于同一坐标，而 Person $1$ 和 Person $2$ 将在派对结束时位于同一坐标。
因此，他们可以满足 $k = 5$ 的所有条件。对于更小的 $k$，无法找到一种策略满足所有条件。

示例输入 2

5
0 2 4 6 8

示例输出 2

3

在持续 $3$ 秒的派对中，每个人应例如按照以下方式移动：

• Person $1$: 总是以速度 $1$ 向正方向移动。
• Person $2$: 前 $2$ 秒内以速度 $1$ 向正方向移动，之后的 $1$ 秒内以速度 $1$ 向负方向移动。
• Person $3$: 不移动。
• Person $4$: 前 $2$ 秒以速度 $1$ 向负方向移动，之后的 $1$ 秒以速度 $1$ 向正方向移动。
• Person $5$: 总是以速度 $1$ 向负方向移动。

示例输入 3

10
0 2 4 6 8 92 94 96 98 100

示例输出 3

44