В ряд стоят $n$ домино одинаковой высоты $h$ ($h_{\min} \le h \le h_{\max}$). $i$-е домино находится в позиции $a_i$.

Лобстер и Мобстер играют в следующую игру. Игроки по очереди роняют домино. В свой ход текущий игрок выбирает одно из домино и роняет его либо влево, либо вправо. Домино падает и, возможно, роняет другие домино.

Одно домино может уронить другое тогда и только тогда, когда расстояние между ними (разность позиций) строго меньше $h$. Например, если домино $i$ находится в позиции $a_i$, а домино $j$ расположено справа от домино $i$ в позиции $a_j$, и $a_j - a_i < h$, то падение домино $i$ вправо также уронит домино $j$. Затем домино $j$ может уронить следующее домино и так далее, пока последнее домино в цепочке падения не перестанет доставать до следующего.

Игра заканчивается, когда все домино упали. Игрок выигрывает, если он роняет последнее оставшееся домино, и проигрывает, если в свой ход он не может уронить ни одного домино, так как все они уже упали.

Лобстер ходит первым, что дает ему преимущество. Поэтому перед началом игры Мобстеру разрешается применить магическое заклинание, которое меняет высоту всех домино с $h$ на произвольное число $h'$, выбранное Мобстером из диапазона $[h_{\min}, h_{\max}]$ (включительно).

Игроки играют оптимально. Найдите минимальную высоту домино $h'$, которая приносит Мобстеру победу, или определите, что любое значение $h'$ ведет к поражению Мобстера.

Входные данные

Первая строка содержит целые числа $n$, $h_{\min}$ и $h_{\max}$ ($1 \le n \le 10^5$, $1 \le h_{\min} \le h_{\max} \le 10^9$). Вторая строка содержит $n$ целых чисел. $i$-е из них — это позиция $a_i$ $i$-го домино ($-10^9 \le a_i \le 10^9$). Гарантируется, что позиции всех домино попарно различны.

Выходные данные

Выведите минимальную высоту $h'$, которая приносит Мобстеру победу, или выведите «-1», если при любом значении $h'$ из диапазона $[h_{\min}, h_{\max}]$ Мобстер проигрывает.

Примеры

Входные данные 1

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

Выходные данные 1

3