Cho một chuỗi số nguyên ~A~ gồm ~n~ phần tử. Một chuỗi con được gọi là "đối xứng" nếu khi đọc từ trái sang phải và từ phải sang trái đều cho cùng một dãy số.

Bạn cần tìm chuỗi con đối xứng có tổng lớn nhất trong chuỗi ~A~.

Note: Giả sử Input chỉ có một Testcase duy nhất.

Input Specification

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên ~A_1, A_2, \dots, A_n~ ~(-10^9 \le A_i \le 10^9)~.

Output Specification

• In ra một số nguyên duy nhất: tổng của chuỗi con đối xứng có tổng lớn nhất.

Constrains

• ~1 \le n \le 10^5~.
• ~-10^9 \le A_i \le 10^9~.

Sample Cases

Input #1:

5
1 2 3 2 1

Output #1:

9

Explanation #1:

Chuỗi con ~[1, 2, 3, 2, 1]~ là đối xứng và có tổng ~= 9~, đây là chuỗi con đối xứng có tổng lớn nhất.

Input #2:

4
-1 2 2 -1

Output #2:

2

Explanation #2:

Chuỗi con ~[2, 2]~ là đối xứng và có tổng ~= 4~, nhưng chuỗi con ~[-1, 2, 2, -1]~ có tổng ~= 2~ và cũng đối xứng. Ta chọn chuỗi có tổng lớn hơn.