Cho số nguyên \(n\) và dãy số nguyên \(a_1,a_2,…,a_n\). Một đoạn con \([L,R]\) của dãy là một dãy con gồm các phần tử liên tiếp \(a_L,a_{L+1},..,a_R\) với \(1≤L<R≤n\). Đoạn con \([L,R]\) được gọi là đẹp nếu \(a_L=a_R.\)

Yêu cầu: Tìm đoạn con đẹp có tổng lớn nhất.

Input

• Dòng thứ nhất chứa số nguyên \(n\).

• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,…,a_n (|a_i |≤10^9,1≤i≤n).\)

Giữa các số trên cùng một dòng cách nhau dấu cách.

Output

• Ghi tổng lớn nhất của đoạn con đẹp tìm được.

Ràng buộc

• Subtask 1: \(n≤10^2.\)

• Subtask 2: \(n≤10^3.\)

• Subtask 3: \(n≤10^5.\)

Sample Input

8
2 5 3 3 5 4 7 4

Sample Output

16