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, \ldots, A_N\).

Một đoạn con \((L, R)\) của dãy là một đoạn các phần tử liên tiếp \(A_L, A_{L+1}, \ldots, A_R\) với \(1 \le L < R \le N\).

Đoạn con được gọi là chứa thông tin quan trọng nếu thoả mãn:

• \(A_L = A_R\)
• Tổng các phần tử trong đoạn là lớn nhất có thể

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

Input

• Dòng đầu chứa số nguyên \(N\) \((1 \le N \le 10^5)\)
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \ldots, A_N\) \((|A_i| \le 10^9)\)

Output

Ghi ra một số nguyên — tổng lớn nhất của một đoạn con \((L, R)\) thoả mãn điều kiện đề bài.

Scoring

• Subtask 1 (40%): \(N \le 100\)
• Subtask 2 (30%): \(N \le 10^3\)
• Subtask 3 (30%): \(N \le 10^5\)

Sample Input 1

7
3 3 3 3 1 11 1

Sample Output 1

13