도미노 게임

길이가 같은 $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가 먼저 두기 때문에 Lobster가 유리하다. 그래서 게임을 시작하기 전에 Mobster는 마법 주문을 사용해 모든 도미노의 높이를 $h$에서 Mobster가 $[h_{\min}, h_{\max}]$ 범위에서 고른 임의의 수 $h'$으로 바꿀 수 있다.

두 사람이 최적으로 플레이할 때, Mobster가 승리하게 되는 도미노 높이 $h'$의 최솟값을 구하라. 어떤 $h'$으로도 Mobster가 이길 수 없다면 그 사실을 판정하라.

첫째 줄에 정수 $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"을 출력한다.