题目内容

机房里一列机柜自下而上有 $n$ 个安装层，编号 $1 \sim n$。第 $i$ 层的基准高度是整数 $a_i$。

要为每一层定一个整数安装高度 $h_i$。所有层共用同一个非负整数偏差 $T$：

• 每一层都满足 $|h_i-a_i|\le T$；
• 从第 $2$ 层起，相邻两层高度相差只能是 $0$ 或 $1$，即 $|h_i-h_{i-1}|\in\{0,1\}$。高度可以升高、保持不变，也可以降低。

请计算最小的 $T$。

输入描述

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

约束

$1 \le n \le 10^5$

$0 \le a_i \le 10^9$

输出描述

输出一个整数，为最小的非负整数 $T$。

样例1

输入

3
0 3 6

输出

2

说明

$T=1$ 时，三层高度只能分别落在 $[-1,1]$、$[2,4]$、$[5,7]$。

第 $2$ 层和第 $3$ 层相差要是 $0$ 或 $1$，只能取 $h_2=4$、$h_3=5$。此时 $h_1$ 还要与 $4$ 相差 $0$ 或 $1$，即 $h_1\in[3,5]$。它和 $[-1,1]$ 没有公共整数，所以 $T=1$ 不可行。

$T=0$ 时高度只能是 $0,3,6$，相邻差为 $3$ 和 $3$，也不可行。

$T=2$ 时可以取 $h=(2,3,4)$：

• $|2-0|=2$，$|3-3|=0$，$|4-6|=2$，偏差都不超过 $2$；
• $|2-3|=1$，$|3-4|=1$，相邻差都合法。

因此最小的 $T$ 是 $2$。

若三层安装成同一个高度，例如 $h=(3,3,3)$，第 $1$ 层和第 $3$ 层的偏差都是 $3$，对应的 $T$ 至少是 $3$，比 $2$ 大。

样例2

输入

3
4 1 3

输出

1

说明

$T=0$ 时高度只能是 $4,1,3$。$|4-1|=3$，不是 $0$ 或 $1$，不可行。

$T=1$ 时可以取 $h=(3,2,2)$：

• $|3-4|=1$，$|2-1|=1$，$|2-3|=1$；
• $|3-2|=1$，$|2-2|=0$。

第 $2$ 层比第 $1$ 层低 $1$，相差仍然允许。因此最小的 $T$ 是 $1$。