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}, \ldots, A_R $$

với

$$ 1 \le L < R \le 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ể.

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 chứa số nguyên dương N.

• Dòng 2 chứa dãy số

  $$ A_1, A_2, \ldots, A_N $$

  với

  $$ 0 < A_i \le 10^3,\quad 1 \le i \le N. $$

Dữ liệu ra

Ghi ra 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ụ

Input

6
2 2 2 3 10 3

Output

16

Giải thích

Đoạn con quan trọng nhất là:

3 10 3

Có tổng các phần tử bằng:

$$ 3 + 10 + 3 = 16. $$

Ràng buộc

• 40% số test tương ứng với 40% số điểm có:

  $$ 2 \le N \le 10^2. $$

• 30% số test tương ứng với 30% số điểm có:

  $$ 2 \le N \le 5 \times 10^3. $$

• 30% số test tương ứng với 30% số điểm có:

  $$ 2 \le N \le 5 \times 10^5. $$