Sơn là một nhà thám hiểm dũng cảm. Trên đảo phiêu lưu có n con quái vật, mỗi con quái vật có một lượng điểm kinh nghiệm nhất định. Sơn có một kỹ năng cho phép bắt một loạt quái vật cùng lúc, nhưng với điều kiện số hiệu của các con quái vật đó phải liên tiếp nhau. Hỏi Sơn nên chọn bắt những con quái vật nào để thu được lượng điểm kinh nghiệm lớn nhất?

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên n. Dòng thứ hai chứa n số nguyên, biểu thị điểm kinh nghiệm của từng con quái vật.

Dữ liệu ra

In ra một số nguyên biểu thị lượng điểm kinh nghiệm lớn nhất.

Ví dụ

Input

5
1 -2 3 4 -1

Output

7

Ghi chú

Giới hạn dữ liệu

n ≤ 10⁵

1: Bài này kiểm tra tổng đoạn con lớn nhất, sử dụng thuật toán Kadane 2: Duy trì tổng đoạn hiện tại và giá trị lớn nhất; nếu tổng hiện tại âm thì bắt đầu lại từ đầu