Cho một dãy số nguyên gồm \(n\) phần tử: \(a_{1},\ a_{2},\ \ldots,\ a_{n}\). Một đoạn con \(\lbrack l,\ r\rbrack\) là dãy gồm các phần tử liên tiếp \(a\_ l,\ a_{l + 1},\ \ldots,\ A_{r}\) với \(1 \leq l < r \leq n\), đoạn con \(\lbrack l,\ r\rbrack\) đượ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ể.

Yêu cầu: 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 đó.

Dữ liệu vào:

• Dòng 1: Lưu số nguyên dương \(n\).

• Dòng 2: Lưu dãy \(a_{1},a_{2},\ldots,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.

Dữ liệu ra:

+ Ghi một số nguyên duy nhất là tổng các phần tử trong đoạn con quan trọng nhất tìm được.

Ví dụ:

Ràng buộc:

• 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 {5.10}^{3}\)_.

• 30% số test tương ứng với 30% số điểm có \(2 \leq n \leq {5.10}^{5}\).