Cho một mảng số nguyên \(a\) độ dài \(n\). Bạn cần chọn ra một mảng con liên tiếp không rỗng của \(a\). Sau khi chọn, bạn được phép xóa tối đa một phần tử khỏi mảng con đó (hoặc giữ nguyên không xóa phần tử nào).

Hãy tìm tổng lớn nhất có thể đạt được của mảng con sau khi thực hiện thao tác trên.

Lưu ý: Mảng con sau khi xóa (nếu có) không được phép rỗng. Nghĩa là nếu bạn chọn mảng con chỉ có 1 phần tử, bạn không được phép xóa phần tử đó.

Input

• Dòng đầu tiên chứa một số nguyên dương \(n\) — số lượng phần tử của mảng.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) cách nhau bởi khoảng trắng.

Output

• In ra một số nguyên duy nhất là tổng lớn nhất có thể đạt được.

Constraints

• \(1 \le n \le 10^5\)
• \(-10^4 \le a_i \le 10^4\)

Example

4
1 -2 0 3

4

4
1 -2 -2 3

3

3
-1 -2 -3

-1

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 500\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 5000\).
• Subtask \(3\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.