(seqnb.*)

Cho một dãy số A gồm \(N\) số nguyên \(A_{1},\ A_{2},\ \ldots,\ A_{N}\). Một đoạn con \(\lbrack L;R\rbrack\) là một dãy các phần tử liên tiếp \(A_{L},\ A_{L + 1},\ldots,A_{R}\ (1 \leq L \leq R\ \leq N)\). Đoạn \(\lbrack L;R\rbrack\) đượ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.

Dữ liệu vào:

- 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},\ \ldots,\ A_{N}\) \((\ \left| A_{i} \right| \leq 10^{3},\ 1\ \leq \ i\ \leq N \leq 5 \times 10^{5})\), mỗi số cách nhau bởi một khoảng trắng.

Dữ liệu ra:

+ Ghi kết quả theo yêu cầu của bài toán.

Ví dụ:

Ràng buộc:

- 30% số test với 1\(\leq N \leq 10^{2}\).

- 40% số test với \(10^{2} < N \leq 5\ \times 10^{5};\ 0 < A_{i} \leq 10^{3}\ (1 \leq i \leq N)\).

- 30% số test còn lại không có ràng buộc gì thêm.