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.