Trên mỗi một trong số \(n\) quân bài có ghi một số nguyên dương nhỏ hơn 1000. Các quân bài được xếp thành một dãy, quân nọ nối tiếp quân kia. Bờm vừa phát minh ra một trò chơi mới. Trò chơi đòi hỏi thực hiện một số bước. Tại mỗi bước phải loại bỏ một trong các quân bài trong dãy, không được phép loại quân bài đầu tiên cũng như quân bài cuối cùng. Đối với mỗi quân bài bị loại bỏ sẽ nhận được số điểm bằng tích của số ghi trên quân bài này với tổng các số ghi trên hai quân bài xếp cạnh nó. Trò chơi kết thúc khi dãy chỉ còn hai quân bài đầu tiên và cuối cùng.

Yêu cầu: Hãy tìm số lượng điểm lớn nhất có thể đạt được từ trò chơi mà Bờm vừa phát hành.

Dữ liệu vào:

+ Dòng đầu tiên chứa số nguyên \(n\ (3\ \leq \ n\ \leq \ 700)\).

+ Dòng tiếp theo chứa \(n\) số nguyên là các số viết trên các quân bài được liệt kê theo thứ tự chúng xuất hiện trên dãy quân bài.

Kết quả:

+ Ghi ra một số nguyên là số lượng điểm lớn nhất tìm được

Ví dụ: