AT_arc120_e [ARC120E] 1D Party

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

第一行一个正整数 $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$ 秒结束时到达同一个位置。

### 制約 - $ 2\ \le\ N\ \le\ 2\ \times\ 10^5 $ - $ 0\ \le\ A_i\ \le\ 10^9 $ - $ A_1\