Cho mảng \(A\) độ dài \(n\). Hợp \(2\) phần tử liên tiếp \(A_i\) và \(A_{i+1}\) sẽ tốn chi phí là \(A_i + A_{i+1}\)

Thực hiện thao tác trên cho đến khi \(A\) chỉ còn một phần tử, hỏi chi phí ít nhất là bao nhiêu?

Dữ liệu vào

• Dòng đầu tiên gồm số nguyên \(n\).
• Dòng thứ hai gồm \(n\) số nguyên \(A_i\).

Dữ liệu ra

• In ra chi phí nhỏ nhất

Điều kiện

• \(1 \le n \le 500\)
• \(1 \le A_i \le 10^9\)

Input 1

4
10 20 30 40

Output 1

190

Giải thích