높이가 $h$ ($h_{\min} \le h \le h_{\max}$)로 동일한 $n$개의 도미노가 일직선상에 놓여 있습니다. $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가 패배한다면 -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