Cho một dãy số nguyên gồm N phần tử A₁, A₂, ..., A_N. Một đoạn con [L, R] là một dãy con gồm các phần tử liên tiếp A_L, A_L+1, ..., A_R với 1 ≤ L ≤ R ≤ N.

Đoạn con [L, R] được gọi là đoạn 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:

Đọc từ file văn bản quantrong.inp có cấu trúc như sau:

Dòng 1: số nguyên dương N là số lượng phần tử của dãy.

Dòng 2: ghi N số nguyên A₁, A₂, ..., A_N (0 < A_i ≤ 10³, 1 ≤ i ≤ N) cách nhau một khoảng trắng.

Kết quả:

Ghi ra file văn bản quantrong.out 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ụ:

quantrong.inp

6

2 2 3 10 3 3

quantrong.out

16

Giải thích:

Đoạn con quan trọng nhất trong dãy là 3 10 3 có tổng bằng 16

Giới hạn:

Subtask 1: 40% số test có 2 ≤ N ≤ 10²</p>

Subtask 2: 30% số test khác có 2 ≤ N ≤ 5 × 10³

Subtask 3: 30% số test cuối cùng có 2 ≤ N ≤ 5 × 10⁵