THỰC HÀNH

Có N lá bài, trên mỗi lá bài ghi một số nguyên dương không vượt quá 1000. Các quân bài được xếp thành một chồng. Người ta lần lượt rút các lá bài bên trong chồng bài (tức là trừ lá bài trên cùng và dưới cùng), mỗi lần rút một quân cho đến khi chỉ còn lại lá trên cùng và dưới cùng. Chi phí rút một lá bài là tích ba số ghi ở lá bài trên lá được rút, lá bài dưới lá được rút và số ghi trên lá bài được rút. Khi rút hết N – 2 lá bài, ta có tổng chi phí rút bài. Mỗi trình tự rút bài sẽ có một tổng chi phí.

Ví dụ, N = 5 và số ghi trên các lá bài là 10, 1, 50, 20, 5. Nếu lần lượt rút các lá bài có các số 1, 20 và 50, thì tổng chi phí là:

10*1*50 + 50*20*5 + 10*50*5 = 500+5000+2500 = 8000

Còn nếu rút các lá với số 50, 20 và 1 thì tổng chi phí sẽ là:

1*50*20 + 1*20*5 + 10*1*5 = 1000+100+50 = 1150

Yêu cầu: Hãy tính tổng chi phí nhỏ nhất khi rút hết N – 2 lá bài.

Dữ liệu vào:

• Dòng đầu ghi số N.
• Dòng thứ hai ghi n số A₁, A₂, …, A_N được ghi trên N lá bài.

Dữ liệu ra:

Ghi ra tổng chi phí nhỏ nhất tìm được.

Ví dụ:

Dữ liệu vào:
5
10 1 50 20 5

Dữ liệu ra:
1150

 Giới hạn: 3 ≤ N ≤ 100; 1 ≤ A_i ≤ 1000.