Cùng với cậu bé Kostek, bạn đang xây các tòa tháp bằng những khối đồ chơi. Hai người đã xây xong $n$ tòa tháp thành một hàng, tòa tháp thứ $i$ có chiều cao $h_i$. Bây giờ Kostek muốn đặt một ranh giới giữa các tòa tháp của cậu ấy và của bạn. Các tòa tháp ở bên trái ranh giới sẽ thuộc về Kostek, và các tòa tháp còn lại ở bên phải sẽ thuộc về bạn. Mỗi người phải có ít nhất một tòa tháp.
Hai bạn sắp chuyển sang trò chơi tiếp theo, bắt đầu bằng việc mỗi người đặt một lính trinh sát lên tòa tháp cao nhất của mình. Trò chơi sẽ không còn vui nếu hai lính trinh sát đứng ở hai độ cao hoàn toàn khác nhau. Do đó, bạn nên đề xuất cách phân chia công bằng nhất có thể – chọn ranh giới sao cho giá trị tuyệt đối của hiệu chiều cao giữa tòa tháp cao nhất của Kostek và của bạn là nhỏ nhất. Hãy in ra hiệu nhỏ nhất này.
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên $n$ ($2 \le n \le 300\,000$), biểu thị số lượng tòa tháp.
Dòng thứ hai chứa $n$ số nguyên $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$), biểu thị chiều cao của các tòa tháp liên tiếp từ trái sang phải.
Kết quả
In ra một số nguyên – chênh lệch chiều cao nhỏ nhất có thể giữa tòa tháp cao nhất của bạn và tòa tháp cao nhất của Kostek.
Ví dụ
Dữ liệu vào 1
3 200 333 100
Kết quả 1
133
Dữ liệu vào 2
5 5 2 4 1 5
Kết quả 2
0
Dữ liệu vào 3
6 5 1 4 4 2 3
Kết quả 3
1
Giải thích
Ở ví dụ đầu tiên, Kostek nên đặt ranh giới giữa hai tòa tháp đầu tiên. Khi đó cậu ấy có một tòa tháp cao $200$, còn bạn có các tòa tháp cao $333$ và $100$. Các tòa tháp cao nhất của mỗi người là $200$ và $333$, vì vậy kết quả là $133$. Không thể đạt được chênh lệch nhỏ hơn.
Ở ví dụ thứ hai, bất kỳ cách phân chia nào cũng cho kết quả chênh lệch bằng $0$.
Ở ví dụ thứ ba, Kostek nên đặt ranh giới sau tòa tháp thứ nhất, thứ hai hoặc thứ ba. Khi đó hiệu cần tìm là $|5 - 4| = 1$. Hình vẽ dưới đây minh họa một trong những phương án tối ưu này:
