有 $n$ 个高度均为 $h$ ($h_{\min} \le h \le h_{\max}$) 的多米诺骨牌排成一行。第 $i$ 个骨牌位于位置 $a_i$。

Lobster 和 Mobster 在玩一个游戏。玩家轮流推倒多米诺骨牌。在每一轮中，当前玩家选择一个尚未倒下的骨牌，并将其向左或向右推倒。骨牌倒下时可能会推倒其他骨牌。

当且仅当两个骨牌之间的距离（位置之差）严格小于 $h$ 时，一个骨牌才能推倒另一个。例如，如果骨牌 $i$ 位于 $a_i$，骨牌 $j$ 位于骨牌 $i$ 的右侧且位置为 $a_j$，若 $a_j - a_i < h$，则向右推倒骨牌 $i$ 也会推倒骨牌 $j$。随后，骨牌 $j$ 可能会推倒下一个骨牌，以此类推，直到连锁反应中最后一个骨牌无法触及下一个骨牌为止。

当所有骨牌都倒下时游戏结束。推倒最后一个骨牌的玩家获胜；如果轮到某位玩家时，由于没有剩余的骨牌可供推倒而无法进行操作，则该玩家失败。

Lobster 先手，这给了他优势。因此，在游戏开始前，Mobster 可以施展一个魔法，将所有骨牌的高度从 $h$ 更改为 Mobster 从范围 $[h_{\min}, h_{\max}]$（包含边界）中选择的任意数值 $h'$。

双方均采取最优策略。请找出能让 Mobster 获胜的最小骨牌高度 $h'$，如果对于范围 $[h_{\min}, h_{\max}]$ 内的任何 $h'$，Mobster 都会输，则输出 "-1"。

输入格式

第一行包含整数 $n, h_{\min}, h_{\max}$ ($1 \le n \le 10^5, 1 \le h_{\min} \le h_{\max} \le 10^9$)。

第二行包含 $n$ 个整数。第 $i$ 个整数表示第 $i$ 个骨牌的位置 $a_i$ ($-10^9 \le a_i \le 10^9$)。保证所有骨牌的位置互不相同。

输出格式

输出能让 Mobster 获胜的最小高度 $h'$，如果对于范围 $[h_{\min}, h_{\max}]$ 内的任何 $h'$，Mobster 都会输，则输出 "-1"。

样例

样例输入 1

10 2 5
20 2 22 -4 0 -5 12 5 10 -9

样例输出 1

3