Mô tả và yêu cầu

Cho dãy số gồm n số nguyên a1, a2, …, an. Một đoạn con của dãy được định nghĩa là dãy ai, ai+1, …, aj với 1 ≤ i ≤ j ≤ n, đoạn con này có chiều dài là (j - i + 1).

Bây giờ ta chọn hai đoạn con X và Y không có phần tử chung và có cùng chiều dài là k (k > 0). Ký hiệu hai đoạn đó là x1, x2, ..., xk và y1, y2, ..., yk. Sau đó tính tổng:

S = x1.yk + x2.yk-1 + … + xk-1.y2 + xk.y1

Yêu cầu: Với các đoạn con X, Y có thể có trong dãy n số trên, hãy tìm giá trị lớn nhất của S.

Dữ liệu vào

Dữ liệu vào: SEQ10.inp
- Dòng thứ nhất là số nguyên n.
- Dòng thứ hai là n số nguyên a1, a2, …, an (|ai| ≤ 10^6 ), mỗi số cách nhau một khoảng trắng.

Dữ liệu ra

Kết quả: SEQ10.out
- Là giá trị lớn nhất của S.

Giới hạn và chấm điểm

Sub1: 60% số test có n ≤ 50.
Sub2: 40% số test còn lại có n ≤ 3000.

Ví dụ

8
2 3 0 3 0 3 2 1

13

X = { 2, 3 }, Y = { 3, 2 }

Ví dụ 2

5
3 2 -9 1 -8

72

X = { -8 }, Y = { -9 }