Dãy số nguyên gồm ~n~ số nguyên dương ~a_{1}, a_{2}, ..., a_{n}~. Một dãy con gồm các số nguyên liên tiếp ~a_{L}, a_{L+1}, ..., a_{R}~ với ~1 \le L < R \le n~ được gọi là dãy số đặc biệt nếu dãy số thỏa mãn hai điều kiện sau:

• Số nguyên đầu tiên bằng số nguyên cuối của dãy con ~(a_{L} = a_{R})~.

• Tổng các số nguyên của dãy con đó là lớn nhất.

Yêu cầu: Đưa ra tổng lớn nhất của dãy số đặc biệt.

Input

• Dòng 1: Là một số nguyên dương ~n~ ~(1 < n \le 10^{5})~.

• Dòng 2: Gồm ~n~ số nguyên ~a_{1}, a_{2}, ..., a_{n}~ ~(0 < a_{i} \le 10^{3})~ cách nhau một dấu cách.

Output

Là tổng lớn nhất của dãy số đặc biệt. In ra ~0~ nếu không tồn tại.

Scoring

Sample Input 1

8
2 4 3 2 3 7 1 3

Sample Output 1

19

Sample Input 2

6
2 2 2 3 10 3

Sample Output 2

16

Sample Input 3

5
1 2 3 4 5

Sample Output 3

0

Notes

• Test 1: Dãy số đặc biệt trong dãy là ~3, 2, 3, 7, 1, 3~ có tổng bằng ~19~.

• Test 2: Dãy số đặc biệt trong dãy là ~3, 10, 3~ có tổng bằng ~16~.

• Test 3: Không tồn tại dãy số đặc biệt.