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.