Có $n$ quân cờ domino có cùng chiều cao $h$ ($h_{\min} \le h \le h_{\max}$) được đặt trên một hàng thẳng. Quân cờ thứ $i$ được đặt tại vị trí $a_i$.

Lobster và Mobster chơi trò chơi sau đây. Các người chơi lần lượt chọn một quân cờ domino và đẩy nó sang trái hoặc sang phải. Quân cờ đổ xuống và có thể làm đổ các quân cờ khác.

Một quân cờ có thể làm đổ quân cờ khác nếu và chỉ nếu khoảng cách giữa chúng (hiệu các vị trí) nhỏ hơn $h$. Ví dụ, nếu quân cờ $i$ ở vị trí $a_i$ và quân cờ $j$ nằm bên phải quân cờ $i$ ở vị trí $a_j$, và $a_j - a_i < h$, thì khi đẩy quân cờ $i$ sang phải, nó sẽ làm đổ quân cờ $j$. Sau đó, quân cờ $j$ có thể làm đổ quân cờ tiếp theo, và cứ tiếp tục như vậy cho đến khi quân cờ cuối cùng trong chuỗi không thể chạm tới quân cờ kế tiếp.

Trò chơi kết thúc khi tất cả các quân cờ đã đổ. Người chơi thắng nếu họ là người đẩy quân cờ cuối cùng, và người chơi thua nếu đến lượt mình mà không thể đẩy quân cờ nào vì không còn quân cờ nào chưa đổ.

Lobster đi trước, điều này mang lại lợi thế cho cậu ấy. Vì vậy, trước khi bắt đầu trò chơi, Mobster được phép sử dụng một phép thuật thay đổi chiều cao của tất cả các quân cờ từ $h$ thành một số $h'$ bất kỳ do Mobster chọn trong khoảng $[h_{\min}, h_{\max}]$ (bao gồm cả hai đầu mút).

Các người chơi chơi tối ưu. Hãy tìm chiều cao tối thiểu $h'$ giúp Mobster giành chiến thắng, hoặc xác định rằng bất kỳ $h'$ nào cũng dẫn đến thất bại cho Mobster.

Dữ liệu vào

Dòng đầu tiên chứa các số nguyên $n$, $h_{\min}$ và $h_{\max}$ ($1 \le n \le 10^5$, $1 \le h_{\min} \le h_{\max} \le 10^9$).

Dòng thứ hai chứa $n$ số nguyên. Số thứ $i$ là vị trí $a_i$ của quân cờ thứ $i$ ($-10^9 \le a_i \le 10^9$). Đảm bảo rằng vị trí của tất cả các quân cờ là phân biệt.

Dữ liệu ra

In ra chiều cao tối thiểu $h'$ giúp Mobster giành chiến thắng, hoặc in ra "-1" nếu với mọi giá trị $h'$ trong khoảng $[h_{\min}, h_{\max}]$, Mobster đều thua.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

3