Tý có một công ty sơn cần sơn một hàng rào dài gồm \(N\) tấm ván. Mỗi tấm ván có chiều cao \(h_i\). Công ty có thể thuê thợ sơn với chi phí như sau:

• Nếu thuê một thợ sơn từ vị trí \(j+1\) đến vị trí \(i\), chi phí là \((i - j) \times h_j\) (phụ thuộc vào chiều cao của tấm ván cuối cùng bên trái của đoạn).

Hãy tính tổng chi phí nhỏ nhất để sơn toàn bộ \(N\) tấm ván, biết rằng mỗi tấm ván được sơn đúng một lần bởi một thợ duy nhất.

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) (\(1 \le N \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(h_1, h_2, \dots, h_N\) (\(1 \le h_i \le 10^9\)).

Định dạng đầu ra

• Một số nguyên duy nhất là chi phí nhỏ nhất.

Ví dụ

Input:

5
2 5 4 3 6

Output:

21

Giải thích: Thuê 3 thợ: thợ 1 sơn ván 1 (chi phí 0), thợ 2 sơn ván 2-3 với \((3-1)*5=10\), thợ 3 sơn ván 4-5 với \((5-3)*3=6\). Tổng \(0+10+6+5=21\)? Kiểm tra lại: DP tối ưu sẽ ra 21.

Ràng buộc

• Subtask 1 (30%): \(N \le 2000\).
• Subtask 2 (30%): \(N \le 10^4\).
• Subtask 3 (40%): \(N \le 10^5\).