Cho dãy \(a_1, \ldots, a_n\). Ta có thể thực hiện thao tác \(\operatorname{reduce}(i)\): thay hai phần tử \(a_i\), \(a_{i+1}\) bằng một phần tử duy nhất có giá trị \(\max(a_i,a_{i+1})\). Dãy nhận được ngắn hơn một phần tử và chi phí của thao tác bằng \(\max(a_i,a_{i+1})\).

Sau \(n-1\) thao tác, dãy chỉ còn một phần tử. Hãy tính tổng chi phí nhỏ nhất của một cách rút gọn dãy như vậy.

Dữ liệu vào

Dòng đầu chứa số nguyên \(n\), độ dài dãy. Mỗi trong \(n\) dòng tiếp theo chứa một số nguyên \(a_i\).

Dữ liệu ra

In ra tổng chi phí nhỏ nhất để rút gọn dãy còn một phần tử.

Ràng buộc

Phân nhóm

• \(30\%\) số phép thử có \(n \le 500\).
• \(50\%\) số phép thử có \(n \le 20\,000\).

Ví dụ

3
1
2
3

5