Cho một dãy số A gồm ~ N ~ số nguyên ~ A_1, A_2, …, 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},…,A_R~ ~(1≤L≤R ≤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.

Dữ liệu vào:

• 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, …, A_N ~ ~ ( A_i≤10^3, 1 ≤ i ≤N≤5×10^5) ~, mỗi số cách nhau bởi một khoảng trắng.

Kết quả:

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

Ví dụ:

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:

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