Cho dãy số gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~. Một đoạn con của dãy được định nghĩa là dãy ~a_i, a_{i+1}, \dots, a_j~ với ~1 \le i \le j \le 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_1, x_2, \dots, x_k~ và ~y_1, y_2, \dots, y_k~. Sau đó tính tổng: ~S = x_1 \times y_k + x_2 \times y_{k-1} + \dots + x_{k-1} \times y_2 + x_k \times y_1~

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~.

Input

• Dòng thứ nhất là số nguyên ~n~ (~2 \le n \le 3000~).
• Dòng thứ hai là ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~|a_i| \le 10^6~), mỗi số cách nhau một khoảng trắng.

Output

• Là giá trị lớn nhất của ~S~.

Sample Input 1

8
2 3 0 3 0 3 2 1

Sample Output 1

13

Sample Input 2

5
3 2 -9 1 -8

Sample Output 2

72