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 ~[h; r]~ là một dãy các điểm số liên tiếp ~A_h, A_{h + 1}, ..., A_r~ ~(1 \le h \le r \le n)~. Đoạn ~[h; r]~ được gọi là một đoạn điểm số đặc biệt nếu ~A_{h} = A_{r}~ và tổng các đ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 đầu vào

Gồm hai dòng:

• Dòng đầu tiên ghi số nguyên dương ~n~ là số lượng quyển sách;
• Dòng thứ hai ghi ~n~ số nguyên ~A_1, A_2, ..., 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.

Dữ liệu đầu ra

Gồm một số nguyên là kết quả theo yêu cầu của bài toán.

Ràng buộc dữ liệu

• Có 30% số test với ~1 \le n \le 10^2~;
• Có 40% số test với ~n \le 5 \times 10^5;\ 0 < A_i \le 10^3;\ \forall\ i \in [1, n]~;
• Có 30% số test còn lại không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

8
5 3 10 3 2 -1 2 9

OUTPUT

16

Ví dụ 2

INPUT

6
5 20 6 1 2 6

OUTPUT

20