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.

Input

• 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 ≤ n ≤ 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 ≤ i ≤ n, 1 ≤ a_i ≤ 10^{18}~).

Output

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

Scoring

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

Example

Input

9
1 3 6 1 5 6 4 7 11

Output

11

Note

Giải thích test mẫu:

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