圆上放置了 $N$ 个机器人。将最北端编号为位置 $0$，把圆等分为 $M$ 份（$M \ge N$），从该位置起按顺时针方向，将其余分点依次编号为 $1$ 到 $M-1$。这样便定义了圆上的位置 $0$ 到 $M-1$（图 1）。最初，机器人位于 $N$ 个互不相同的位置。

圆上两个位置 $x$ 和 $y$ 之间的距离定义为 $y-x$（$y \ge x$）。位于位置 $x_i$ 的机器人 $R_i$ 可以监视自身逆时针和顺时针两个方向上固定范围 $R>0$ 内的点。换言之，设从 $x_i$ 逆时针距离 $R$ 的位置为 $a$，顺时针距离 $R$ 的位置为 $b$，则机器人 $R_i$ 可以监视圆上从 $a$ 顺时针到 $b$ 的部分。

我们希望监视整个圆。机器人的初始位置可能无法监视某些部分，此时需要移动机器人，使整个圆都受到监视。假设 $M \le 2RN$，这样始终能找到一种移动方案，使整个圆都受到监视。

机器人移动时只能移动到上述定义的圆上位置，每个机器人最多移动一次。我们希望最小化机器人移动距离的最大值。

例如，在下方图 1 中，三个机器人 $R_1,R_2,R_3$ 分别位于位置 $1,2,5$，监视范围为 $R=2$。为了监视整个圆，机器人 $R_1$ 移动到位置 $0$，机器人 $R_3$ 移动到位置 $6$。这种移动使机器人移动距离的最大值最小。

图 1

给定 $N$ 个机器人的位置、范围 $R$ 和整数 $M$，求出并输出：移动机器人使整个圆都受到监视时，最大移动距离的最小值。

输入格式

标准输入给出如下信息。第一行给出机器人的数量 $N$（$1 \le N \le 1,000,000$）。第二行给出两个整数 $R$ 和 $M$，分别定义机器人的监视范围及圆上的位置（$1 \le R,M \le 10^9$，$N \le M \le 2RN$）。下一行给出 $N$ 个互不相同的整数 $x_i$（$0 \le x_i \le M-1$，$i=1,\ldots,N$），以空格分隔，表示机器人的初始位置。

子任务

• 子任务 1：占总分 100 分中的 10 分；$M \le 10$。

• 子任务 2：占总分 100 分中的 30 分；$N \le 7,000$。

• 子任务 3：占总分 100 分中的 60 分；除原有限制外，没有其他限制。

输出格式

向标准输出输出使整个圆受到监视时，机器人最大移动距离的最小值。

样例

输入格式 1

3
2 10
1 2 5

输出格式 1

1

输入格式 2

6
1 11
0 1 2 3 4 5

输出格式 2

2