题目描述

有 $N$ 个人打算开派对，他们均分布在数轴上，编号从 $1$ 到 $N$，第 $i$ 个人位于 $a_i$ 点。初始是他们都位于数轴上不同的点。具体的，所有人所在的点都是偶数点，且有 $a_1 < a_2 < a_3 <\cdots< a_n$。

派对计划进行 $k$ 秒，每个人每秒钟可以在数轴上向左或者向右移动一个单位长度，也可以不移动。

我们都知道，开派对至少要两个人。所以派对成功举行的条件是，对于任意的某个人 $j (1≤j<N)$，经过一系列移动过程，在派对进行中至少有一瞬间（包括派对结束的那一刻）使得 $a_j = a_{j+1}$（以当前那一秒结束时的位置为准）。

请计算能够使得派对成功举行的最小的 $k$。

能够证明在题目限定条件下答案一定存在。

输入格式

第一行一个正整数 $N$。
第二行包含 $N$ 个正整数表示 $a_i$。

输出格式

一行一个整数，表示满足条件的最小 $k$ 值。

样例解释

样例 1 解释

我们依次把 $3$ 个人记为 $A,B,C$，在 $5$ 秒内，每个人可以进行如下方式的移动：

• $A$ 一直向右移动；
• $B$ 前 $2$ 秒向右移动，后 $3$ 秒向左移动；
• $C$ 一直向左移动。

这样 $B$ 和 $C$ 在第 $2$ 秒结束时到达同一个位置，$A$ 和 $B$ 在第 $5$ 秒结束时到达同一个位置。

样例 2 解释

我们依次把 $5$ 个人记为 $A,B,C,D,E$。

• $A$ 一直向右移动；
• $B$ 前 $2$ 秒向右移动，后 $1$ 秒向左移动；
• $C$ 一直保持不动；
• $D$ 前 $2$ 秒向左移动，后 $1$ 秒向右移动；
• $E$ 一直向左移动；

这样 $(B,C),(C,D)$ 同时在第 $2$ 秒结束时到达同一个位置，$(A,B),(D,E)$ 分别在第 $3$ 秒结束时到达同一个位置。

样例 1

输入

3
0 6 10

输出

5

样例 2

输入

5
0 2 4 6 8

输出

3

样例 3

输入

10
0 2 4 6 8 92 94 96 98 100

输出

44

说明/提示

限制条件

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