Steve cảm thấy rất mệt mỏi khi phải đi bộ lên cầu thang, trạng thái thừa cân đã ảnh hưởng nhiều đến sức khỏe. Steve quyết định tăng cường rèn luyện thể lực bằng môn thể thao mà mình ưa thích – đi xe đạp vượt địa hình.

Vùng ngoại ô gần nhà của Steve có một con đường đồi, trên đó có thể xác định n điểm, từ điểm i đến điểm i+1 là đoạn chỉ xuống dốc, nằm ngang hoặc chỉ lên dốc (i = 1 ÷ n-1). Điểm 1 và điểm n là các điểm đầu và cuối của con đường, h_i là độ cao tại điểm thứ i (i = 1 ÷ n). Steve không quan tâm lắm đến độ dài của mỗi đoạn đường mà chỉ lưu ý đến chênh lệch độ cao và cũng phải chọn các đoạn đường leo dốc, tức là đi từ thấp lên cao mới có tác dụng rèn luyện tốt. Vì vậy đường đạp xe phải là các đoạn lên dốc liên tục và chênh lệch độ cao ở các điểm đầu và cuối phải lớn nhất. Ví dụ, con đường đồi có 8 điểm với các h_i tương ứng là 12, 3, 5, 7, 10, 6, 1, 11. Các đoạn đường lên dốc liên tục là từ điểm 2 đến điểm 5 với chênh lệch độ cao là 7 và đoạn từ điểm 7 đến điểm 8 với chênh lệch độ cao là 10 và Steve sẽ chọn đường đi từ điểm 7 tới điểm 8.

Yêu cầu: Cho n và các h_i (2 ≤ n ≤ 10⁵, 1≤ h_i ≤ 10⁶, i = 1 ÷ n). Hãy xác định chênh lệch độ cao lớn nhất của đường đạp xe mà Steve có thể chọn.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên n,

• Dòng thứ 2 chứa n số nguyên h₁, h₂, . . ., h_n.

Kết quả:

Ghi một số nguyên – chênh lệch độ cao lớn nhất của đường đạp xe. Nếu không tồn tại đoạn đường lên dốc nào thì đưa ra số 0.

Ví dụ: