Cho dãy số gồm n số nguyên a₁, a₂,..., a_n. Một đoạn con của dãy được định nghĩa là dãy a_i, a_i+1, ... , a_j (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à x₁, x₂, ... , x_k và y₁, y₂, ..., y_k. Sau đó tính tổng:

                 S = x₁. y_k + x₂. y_k-1 + ... + x_k-1. y₂ + x_k. y₁

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òng thứ nhất là số nguyên n (n <= 3000)

                 - Dòng thứ hai là n số nguyên a₁, a₂,..., a_n. (|a_i| ≤ 10⁶), mỗi số cách nhau một khoảng trắng.

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