Một kho hàng lớn chứa nhiều kiện hàng có khối lượng khác nhau. Để chuyển hết hàng trong kho đến bến cảng người ta dùng các xe tải có sức chở bằng nhau. Xếp xong hàng vào xe tải này rồi mới tiếp tục xếp hàng vào xe tải khác. Do phải đi qua một tuyến đường đang sửa chữa nên cần phải bố trí xe tải có sức chở nhỏ nhất có thể để vận chuyển hàng.

Yêu cầu: Cho biết thứ tự và khối lượng các kiện hàng được lấy ra từ kho. Tính xe tải có sức chở nhỏ nhất là bao nhiêu để khi xếp hàng, tất cả các xe tải đều được xếp vừa đủ sức chở mà không phải chia nhỏ các kiện hàng.

Dữ liệu vào:

+ Dòng thứ nhất chứa 1 số nguyên dương \(n\) là số lượng kiện hàng của kho; \((5 \leq n \leq 10^{6})\)

+ Dòng thứ 2 chứa \(n\) số nguyên dương \(a_{1},\ a_{2},..a_{n}\) (mỗi số cách nhau một khoảng trắng), trong đó \(a_{i}\) là khối lượng của kiện hàng thứ \(i\).\((1 \leq i \leq n,1 \leq a_{i} \leq 10^{18})\)

Dữ liệu ra:

+ Ghi một số nguyên duy nhất là sức chở của xe tải được bố trí.

Ví dụ:

Ràng buộc:

+ Có 20% số test tương ứng 20% số điểm với \((5 \leq n < 10^{2},1 \leq a_{i} < 10^{9})\)

+ Có 40% số test tương ứng 40% số điểm với \((10^{2} \leq n < 10^{4},1 \leq a_{i} < 10^{9})\)

+ Có 20% số test tương ứng 20% số điểm với \((10^{4} \leq n \leq 10^{6},1 \leq a_{i} < 10^{9})\)

+ Có 20% số test tương ứng 20% số điểm với \((10^{4} \leq n \leq 10^{6},10^{9} \leq a_{i} < 10^{18})\)