共享单车是一种受欢迎的通勤方式。但有时令人沮丧的是，一些单车停放点几乎没有车，而另一些停放点却几乎停满，几乎没有空位。单车公司定期派遣卡车重新分配单车以缓解这些问题。

一辆卡车即将从单车中心出发，开始一次单车重分配之旅。卡车最多可装载 $c$ 辆单车。在从单车中心出发之前，它可以选择装载 $0$ 到 $c$ 辆（含边界）单车作为其初始载车量。然后，卡车将按顺序访问 $n$ 个停放点。每个停放点最多可停放 $d$ 辆单车。起初，每个停放点已经停放了一些单车。在每个停放点，卡车可以装载或卸载任意数量的单车，只要不超过卡车或该停放点的容量限制。在旅程结束时，卡车不需要携带与初始载车量相同数量的单车。单车重分配的目标是最小化所有停放点中单车数量的最大值与最小值之间的差值。

能够达到的最小差值是多少？

输入格式

第一行包含三个整数 $n$、$d$ 和 $c$（$2 \le n \le 2 \cdot 10^5$，$1 \le d, c \le 10^6$），分别表示停放点的数量、停放点的容量以及卡车的容量。

接下来的 $n$ 行，每行包含一个介于 $0$ 到 $d$ 之间（含边界）的整数，表示第 $i$ 个停放点初始拥有的单车数量。

输出格式

输出一个整数，表示所有停放点中单车数量的最大值与最小值之间能够达到的最小差值。

样例

输入样例 1

4 7 3
0
7
2
5

输出样例 1

1