Có ~n~ lá bài (~3 \le n \le 100~), trên mỗi lá bài ghi 1 số nguyên dương không quá 10000 các quân bài xếp thành 1 chồng. Người ta lần lượt rút các lá bài bên trong chồng (trừ lá trên cùng và dưới cùng), mỗi lần rút 1 quân đến khi còn 2 lá bài trên và dưới cùng. Giá rút 1 lá bài là tích 3 số ghi trên lá được rút, lá dưới lá được rút, lá trên lá đượ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 khác nhau có tổng chi phí rút khác nhau.

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 1 chứa số ~N~.
• Dòng 2 chứa ~N~ số nguyên dương ~\le 10000~ là các số ghi trên lá bài.

Output

• Ghi ra 1 số duy nhất là chi phí nhỏ nhất khi rút được ~n - 2~ lá bài.