Tý có \(N\) quả bóng bay được xếp thành một hàng ngang từ trái sang phải, được đánh số từ 1 đến N. Quả bóng thứ i có gắn một số nguyên dương \(a_i\).

Mỗi lượt, bạn có thể chọn bắn nổ một quả bóng \(i\) bất kỳ đang còn lại trên hàng. Khi bắn nổ quả bóng \(i\), bạn sẽ nhận được số điểm bằng: \(a_{L} \times a_i \times a_{R}\) Trong đó \(a_L\) và a_R lần lượt là giá trị ghi trên quả bóng liền kề bên trái và bên phải của quả bóng i tại thời điểm đó. Nếu không còn quả bóng nào ở bên trái (hoặc bên phải), giá trị tương ứng quy ước là \(1\).

Sau khi quả bóng \(i\) bị bắn nổ, các quả bóng còn lại sẽ dịch lại gần nhau. Hãy tìm tổng số điểm lớn nhất mà bạn có thể đạt được sau khi bắn nổ toàn bộ \(N\) quả bóng.

Định dạng đầu vào

• Dòng thứ nhất chứa số nguyên dương \(N\) (\(1 \le N \le 500\)).
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 100\)).

Định dạng đầu ra

• In ra một số nguyên duy nhất là tổng điểm lớn nhất có thể đạt được.

Ví dụ

Input:

3
2 6 6

Output:

90

Giải thích:

• Lượt 1: Bắn quả bóng thứ hai (\(a_2 = 6\)). Điểm nhận được: \(2 \times 6 \times 6 = 72\). Hàng còn lại \([2, 6]\).
• Lượt 2: Bắn quả bóng thứ nhất (\(a_1 = 2\)). Điểm nhận được: \(1 \times 2 \times 6 = 12\). Hàng còn lại \([6]\).
• Lượt 3: Bắn quả bóng cuối cùng (\(a_3 = 6\)). Điểm nhận được: \(1 \times 6 \times 1 = 6\).
• Tổng điểm: \(72 + 12 + 6 = 90\).

Ràng buộc & Subtasks