Ngày hội đọc sách được tổ chức định kỳ tại trường THCS A. Mỗi quyển sách trong thư viện trường có một điểm số đại diện cho độ phổ biến của nó. Có n quyển sách trong thư viện được đánh số thứ tự từ \(1\) đến \(n\) tương ứng với điểm số là các số nguyên \(A_1, A_2, ..., A_n\).

Một đoạn con \([i..j]\) (với \(1 \le i \le j \le n\)) được gọi là đoạn điểm số đặc biệt nếu thỏa mãn: \(A[i]=A[j]\) và tổng điểm số của đoạn này là lớn nhất.

Yêu cầu

• Hãy đưa ra tổng của đoạn điểm số đặc biệt.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương n là số quyển sách.
• Dòng thứ hai chứa n số nguyên \(A_1, A_2, ..., A_n\) \((|A_i| \le 10^4, 1 \le i \le n \le 5.10^5)\), mỗi số cách nhau bởi một khoảng trắng.

Dữ liệu ra

• Kết quả theo yêu cầu của bài toán.

Input 1

8
5 3 10 3 2 -1 2 9

Output 1

16

Input 2

6
5 20 6 1 2 6

Output 2

20

Ràng buộc

• Có 30% số test với \(1 \le n \le 10^2\).
• Có 40% số test với \(n \le 5.10^4; 0 \le |Ai| \le 10^4; 1 \le i \le n\).
• Có 30% số test còn lại không có ràng buộc phụ thêm.