Có ~N~ lá bài ~(3 ≤ N ≤ 100)~, 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.

Input:

Dòng đầu tiên ghi số ~N~.

Dòng thứ hai ghi ~N~ số ~A_1, A_2, ..., A_n~ là các số ghi trên lá bài.

Output:

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

Sample Input 1

5
10 1 50 20 5

Sample Output 1

1150