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 đầu vào

Gồm hai dòng:

• Dòng thứ nhất chứa một số nguyên dương ~n~ là số lượng kiện hàng của kho ~(5 \le n \le 10^6)~;
• Dòng thứ hai 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 \le i \le n,\ 1 \le a_i \le 10^{18})~.

Dữ liệu đầu ra

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

Ràng buộc dữ liệu

• Có 20% số test tương ứng 20% số điểm với ~(5 \le n < 10^2,\ 1 \le a_i < 10^9)~;
• Có 40% số test tương ứng 40% số điểm với ~(10^2 \le n < 10^4,\ 1 \le a_i < 10^9)~;
• Có 20% số test tương ứng 20% số điểm với ~(10^4 \le n \le 10^6,\ 1 \le a_i < 10^9)~;
• Có 20% số test tương ứng 20% số điểm với ~(10^4 \le n \le 10^6,\ 10^9 \le a_i < 10^{18})~.

Ví dụ

Ví dụ 1

INPUT

9
1 3 6 1 5 6 4 7 11

OUTPUT

11

Giải thích: Có ~3~ cách lựa chọn:

• Cách ~1~: ~1~ xe tải có sức chở ~44~.
• Cách ~2~: ~2~ xe tải có sức chở ~22~.
• Cách ~3~: ~4~ xe tải có sức chở ~11~.

Trong đó, cách ~3~ là thỏa mãn yêu cầu sức chở nhỏ nhất.