Description

有 $N$ 个人，分别记为 $1$ 到 $N$，站在一条数轴上。第 $i$ 个人现在站在坐标 $A_i$ 上。其中，$A_1 < A_2 < \cdots < A_N$，并且所有 $A_i$ 都是偶数。

小 h 将举办一个持续 $k$ 秒的银趴。

银趴期间，每个人都可以最快以每秒 $1$ 单位长度的速度在数轴上自由移动（可以向正方向也可以向负方向）。

要求对 $1 \leq i < N$ 中的每一个整数 $i$ 都满足以下条件：

• 在银趴期间至少存在一个时刻（包括聚会结束的时刻），第 $i$ 个人和第 $i + 1$ 个人在同一个坐标上。

请你寻找到最小的持续时间 $k$，使得对于这个 $k$，我们可以采取一定的移动策略来满足上述条件。

在本题中，可以证明答案是一个整数。

Format

Input

第一行有一个整数 $N$ $(2 \leq N \leq 2 \times 10 ^ 5)$，派对中人的个数。

第二行有 $N$ 个整数 $A_1, A_2, \cdots, A_N$ $(0 \leq A_1 < A_2 < \cdots < A_N \leq 10^9)$ ，表示每个人的起始坐标，并且所有 $A_i$ 都是偶数。

Output

输出一个整数，表示银趴持续的最短时间。

Samples

3
0 6 10

5

Note

在这 $5$ 秒中，每个人可以按照下列要求来移动：

• 第 $1$ 个人：持续以 $1$ 的速度向正方向移动；
• 第 $2$ 个人：在前 $2$ 秒内持续以 $1$ 的速度向正方向移动，在剩下的 $3$ 秒内持续以 $1$ 的速度向正方向移动；
• 第 $3$ 个人：持续以 $1$ 的速度向负方向移动。

如果他们以这种方式移动，则第 $2$ 个人和第 $3$ 个人将在开始后正好 $2$ 秒时处于同一坐标，而第 $1$ 个人和第 $2$ 个人将在派对结束时处于相同坐标。

5
0 2 4 6 8

3

Note

在这 $3$ 秒中，每个人可以按照下列要求来移动：

• 第 $1$ 个人：持续以 $1$ 的速度向正方向移动；
• 第 $2$ 个人：在前 $2$ 秒内持续以 1 的速度向正方向移动，在剩下的 $1$ 秒内持续以 $1$ 的速度向正方向移动；
• 第 $3$ 个人：始终不移动；
• 第 $4$ 个人：在前 $2$ 秒内持续以 1 的速度向负方向移动，在剩下的 $1$ 秒内持续以 $1$ 的速度向正方向移动；
• 第 $5$ 个人：持续以 $1$ 的速度向负方向移动。

10
0 2 4 6 8 92 94 96 98 100

44

Limitation

1s, 1024KiB for each test case.