Đoạn con hoàn hảo nhất

Cho một dãy $A$ gồm $N$ số nguyên $A_1, A_2, \dots, A_N$. Một đoạn con $[L; R]$ là một dãy các phần tử liên tiếp $A_L, A_{L+1}, \dots, A_R$ $(1 \le L \le R \le N)$. Đoạn $[L; R]$ được gọi là một đoạn con hoàn hảo nhất nếu phần tử đầu bằng phần tử cuối $(A_L = A_R)$ và tổng các phần tử của đoạn này là lớn nhất.

Yêu cầu: Hãy lập trình đưa ra tổng của đoạn con hoàn hảo nhất.

Trong tệp văn bản SEQ.INP có cấu trúc như sau:

• Dòng đầu tiên ghi số nguyên dương $N$ là số lượng phần tử của dãy $A$.
• Dòng thứ hai ghi $N$ số nguyên $A_1, A_2, \dots, A_N$ ($|A_i| \le 10^3, 1 \le i \le N \le 5 \times 10^5$), mỗi số cách nhau bởi một khoảng trắng.

Tệp văn bản SEQ.OUT ghi kết quả theo yêu cầu của bài toán.

• 30% số test với $1 \le N \le 10^2$.
• 40% số test với $10^2 < N \le 5 \times 10^5$; $0 < A_i \le 10^3$ $(1 \le i \le N)$.
• 30% số test còn lại không có ràng buộc gì thêm.