Cho dãy ~n~ ma trận liên tiếp, trong đó ma trận thứ ~i~ có kích thước ~a_i \times a_{i+1}~. Vì phép nhân ma trận có tính kết hợp, ta có thể chọn thứ tự đặt dấu ngoặc khác nhau khi nhân toàn bộ dãy ma trận, và số phép nhân vô hướng cần thực hiện có thể khác nhau. Hãy tính số phép nhân ít nhất cần dùng để nhân hết dãy ma trận này.

Yêu cầu

Tìm giá trị nhỏ nhất của tổng số phép nhân vô hướng cần thực hiện để tính tích của ~n~ ma trận đã cho.

Dữ liệu

• Dòng đầu chứa số nguyên dương ~n~.
• Dòng thứ hai chứa ~n+1~ số nguyên dương ~a_1, a_2, \ldots, a_{n+1}~.
• Ma trận thứ ~i~ có ~a_i~ dòng và ~a_{i+1}~ cột.

Kết quả

In ra một số nguyên duy nhất là số phép nhân ít nhất cần thực hiện.

Ví dụ

Ví dụ 1

Input

3
4 3 5 3

Output

81

Giải thích

Ví dụ 1

Có ~3~ ma trận với kích thước lần lượt là ~4 \times 3~, ~3 \times 5~, ~5 \times 3~.

• Nếu nhân theo thứ tự ~((A \times B) \times C)~ thì số phép nhân là ~4 \times 3 \times 5 + 4 \times 5 \times 3 = 120~.
• Nếu nhân theo thứ tự ~(A \times (B \times C))~ thì số phép nhân là ~3 \times 5 \times 3 + 4 \times 3 \times 3 = 81~.

Do đó đáp án là ~81~.

Lưu ý: trong ví dụ trên, sau khi tính ~(B \times C)~, ma trận thu được có kích thước ~3 \times 3~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 500~
• ~1 \le a_i \le 1000~