Cho một dãy số nguyên gồm ~N~ phần tử: ~a_1, a_2, ..., a_N~. Một đoạn con ~[L, R]~ là dãy gồm các phần tử liên tiếp ~a_L, a_{L+1}, ..., a_R~ với ~(1 \leq L < R \leq N)~, đoạn con ~[L, R]~ được gọi là quan trọng nhất nếu:

• Phần tử đầu bằng phần tử cuối ~A_L = A_R~
• Tổng các phần tử của đoạn con là lớn nhất có thể.

Input

• Dòng 1: Gồm số nguyên dương ~N~.
• Dòng 2: Gồm dãy ~A_1, A_2, ..., A_N~ (~0 < A_i \leq 10^3, 1 \leq i \leq N)~, mỗi số cách nhau một khoảng trắng.

Output

Tìm một đoạn con quan trọng nhất và tính tổng các phần tử trong đoạn con đó.

Sample Test

Input:

6
2 2 2 3 10 3

Output:

16

Đoạn con quan trọng nhất ~3, 10, 3~ có tổng các phần tử là ~16~

Note

• 40% số test tương ứng với 40% số điểm có ~2 \leq N \leq 10^2~
• 30% số test tương ứng với 30% số điểm có ~2 \leq N \leq 10^3~
• 30% số test tương ứng với 30% số điểm có ~2 \leq N \leq 10^6~