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 \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.

Input

Đọc từ file văn bản SEQNB.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, … , 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.

Output

Ghi ra file văn bản SEQNB.out kết quả theo yêu cầu của bài toán.

Ràng buộc

• ~1 \le N \le 5 \times 10^5~
• ~|A_i| \le 10^3~ với ~1 \le i \le N~

Sample Input 1

8
5 3 10 3 2 -1 2 9

Sample Output 1

16

Giải thích: Đoạn con hoàn hảo nhất là đoạn ~[2; 4]~, gồm ba phần tử ~3; 10; 3~ có tổng bằng ~16~.

Sample Input 2

6
5 20 6 1 2 6

Sample Output 2

20

Giải thích: Đoạn con hoàn hảo nhất là đoạn ~[2; 2]~, gồm một phần tử ~20~ có tổng bằng ~20~.