题目描述

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

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

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

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

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

输入格式

共 $2$ 行：

第一行，一个正整数 $N$

第二行，包含 $N$ 个正整数 $a_i$

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

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

$A$ 一直向右移动；

$B$ 前2秒向右移动，后3秒向左移动；

$C$ 一直向左移动。

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

我们依次把 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 秒结束时到达同一个位置。