BULLDOZER
Bin mua một mảnh đất có chiều rộng \(1\) mét và chiều dài \(N\) mét, được tạo thành từ \(N\) ô liên tiếp, các ô được đánh số từ trái sang phải, từ 1 đến \(N\) và mỗi ô có chiều dài \(1\) mét. Trên các ô đều có các đống đất, đống đất tại ô thứ \(i\) có chiều cao \(h[i]\). Bin muốn san bằng các đống đất này để tất cả các đống đất đều có chiều cao là \(H\).
Bin thuê một chiếc máy ủi, ban đầu bàn ủi trên máy ủi có lượng đất là \(C = 0\) mét khối. Máy ủi bắt đầu đi từ trái sang phải, khi nó đến ô thứ \(i\) , tùy thuộc vào chiều cao h[i] của đống đất \(i\) sẽ có một trong hai trường hợp sau:
Nếu \(h[i] ≥ H\) thì lượng đất \(h[i] – H\) được thêm vào bản ủi.
Nếu \(h[i] < H\) thì máy ủi phải đổ thêm lượng \(H – h[i]\) bàn ủi cho đống đất.
Sau khi máy ủi đi qua \(N\) ô đất, bạn không cần quan tâm trên bàn ủi còn đất hay không còn đất.
Yêu cầu: Hãy tính độ cao \(H\) lớn nhất có thể đạt được.
Dữ liệu:
Dòng đầu tiên chứa số tự nhiên \(N (1 ≤ N ≤ 10^6)\);
Dòng thứ hai chứa \(N\) số tự nhiên \(h[1], h[2], …, h[N] (1 ≤ h[i] ≤ 10^9)\).
Kết quả:
Ghi ra một số nguyên dương duy nhất là chiều cao \(H\) lớn nhất đạt được.
Sample Input
4
5 2 1 6Sample Output
2Có 50% test với \(N ≤ 1000, h[i] < 1000\)
Comments
1