Cho một dẫy số nguyên gồm \(N\) phần tử : \(a_1, a_2, a_3,...., a_n\). Một đoạn con [L,R] lf dãy 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 trong 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ể

Yêu cầu:

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

Input:

• Dòng 1: Số nguyên N
• DÒng 2: Lưu dãy \(a_1, a_2, a_3,...., a_n\). \((0 \leq a_i \leq 10^3, 1 \leq i \leq N)\), mỗi số cách nhau một khoảng trắng.

Output:

• Tổng các phần tử trong đoạn con quan trọng tìm được.

Example

subtask

• 40% số test tương ứng với 40% số điểm có \(2 \leq 10^2\)
• 30% số test tương ứng với 30% số điểm có \(2 \leq 10^3\)
• 30% số test tương ứng với 30% số điểm có \(2 \leq 2.10^5\)