高さ $h$ ($h_{\min} \le h \le h_{\max}$) の $n$ 個のドミノが一直線上に並んでいる。$i$ 番目のドミノは位置 $a_i$ にある。

Lobster と Mobster は以下のゲームを行う。プレイヤーは交互にドミノを倒す。各ターンにおいて、現在のプレイヤーはドミノを1つ選び、左または右に倒す。ドミノが倒れると、他のドミノも倒れる可能性がある。

あるドミノが別のドミノを倒せるのは、それらの間の距離（位置の差）が $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'$ を選んでも Mobster が敗北する場合は -1 を出力せよ。

入力

1行目には整数 $n, h_{\min}, h_{\max}$ ($1 \le n \le 10^5, 1 \le h_{\min} \le h_{\max} \le 10^9$) が与えられる。

2行目には $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