有 $n$ 個高度皆為 $h$ ($h_{\min} \le h \le h_{\max}$) 的骨牌放置在一直線上。第 $i$ 個骨牌位於位置 $a_i$。

Lobster 和 Mobster 進行以下遊戲。玩家輪流推倒骨牌。在每一回合中，當前玩家選擇其中一個骨牌，並將其向左或向右推倒。骨牌倒下時可能會推倒其他骨牌。

一個骨牌可以推倒另一個骨牌的條件是：它們之間的距離（位置差）嚴格小於 $h$。例如，若骨牌 $i$ 位於 $a_i$，而位於骨牌 $i$ 右側的骨牌 $j$ 位於 $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