Hôm nay, các bạn nhỏ ABC Smart lại được Thầy giáo đố một bài toán sau: Cho một dãy số nguyên ~a_1, a_2,..., a_n~. Các phần tử trong dãy được sắp xếp theo trình tự tăng dần, tức là ~a_i \le a_{i+1}~ với mọi ~1 ≤ i < n~. Ta định nghĩa độ đẹp của dãy ~a~ là khoảng cách lớn nhất giữa hai phần tử liên tiếp bất kì trong dãy. Nói cách khác, độ đẹp của dãy ~a~ là giá trị ~a_i – a_{i-1}~ lớn nhất với mọi ~2 ≤ i ≤ n~.

Yêu cầu:

• Hãy xoá một phần tử bất kì trong dãy a sao cho độ đẹp của dãy nhận được là lớn nhất có thể.

Dữ liệu vào:

• Dòng đầu tiên là số nguyên dương ~n (3 ≤ n ≤ 10^6)~;
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2,..., a_n (|a_i| ≤ 2.10^9)~.

Kết quả:

• Ghi ra một số nguyên là độ đẹp của dãy sau khi đã xoá 1 phần tử.

Ví dụ

Ràng buộc:

• Có 50% số điểm có ~n ≤ 10^4~ và ~a_i ≤ 10^9~;
• Có 50% số điểm là các trường hợp còn lại.