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 a1, a2,..., an. Các phần tử trong dãy được sắp xếp theo trình tự tăng dần, tức là ai ≤ ai+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ị ai – ai-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 từ file BAI2.INP gồm: + Dòng đầu tiên là số nguyên dương n (3 ≤ n ≤ 106); + Dòng thứ hai chứa n số nguyên a1, a2,..., an (|ai| ≤ 2.109). Kết quả: Ghi ra file BAI2.OUT một số nguyên là độ đẹp của dãy sau khi đã xoá 1 phần tử. BAI2.INP BAI2.OUT Giải thích 4 2 4 5 6 3 Ta xoá đi phần tử thứ 2 của dãy, thì được dãy là 2, 5, 6. Suy ra độ đẹp bằng 3. Ràng buộc: + Có 50% số điểm có n ≤ 104 và ai ≤ 109; + Có 50% số điểm là các trường hợp còn lại.