Dãy số

Bob gửi cho Alice một dãy số nguyên gồm \(N\) phần tử: \(A_1,A_2,...,A_N\) đây là thông tin về một kho báu. Một đoạn con \((L,R)\) của dãy là một dãy gồm các phần tử liên tiếp \(A_L,A_{L+1},...,A_R\) với \(1\leq L<R\leq N\), đoạn con \((L,R)\) được gọi là chứa thông tin quan trọng nhất nếu:

• Phần tử đầu tiên bằng phần tử cuối cùng (\(A_L=A_R\)).
• Tổng các phần tử của đoạn là lớn nhất có thể.

Hãy giúp Alice tìm đoạn con chứa thông tin quan trọng nhất.

Input

• Dòng thứ nhất chứa số nguyên dương \(N\).
• Dòng thứ hai chứa số nguyên \(A_1,A_2,...,A_N\text{ }(|A_i|\leq 10^9,1\leq i\leq N)\).

Output

Ghi ra thiết bị ra chuẩn một số nguyên duy nhất là tổng của đoạn con chứa thông tin quan trọng nhất.

Example

7
3 3 3 3 1 11 1

13

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N\leq 10^2\)
• Subtask \(2\) (\(30\%\) số điểm): \(N\leq 10^3\)
• Subtask \(3\) (\(30\%\) số điểm): \(N\leq 10^5\)