Đề bài

Cho số nguyên dương n và dãy số nguyên \(A_1, A_2, ,...,A_n\). Với dãy số nguyên này ta có thể thực hiện phép xử lý Reduce(i) thay thế 2 phần tử \(A_i\) và \(A_{i+1}\) bằng \(max(A_i,A_{i+1})\) với chi phí là \(max(A_i,A_{i+1})\).

Sau n - 1 lần thực hiện phép xử lý trên, ta được dãy số độ dài 1. Chi phí biến đổi dãy được tính bằng tổng chi phí của tất cả các phép xử lý đã thực hiện.

Yêu cầu: Cho \(n\) và các số \(A_i\). Hãy xác định chi phí nhỏ nhất đưa dãy về độ dài bằng 1.

Dữ liệu vào:

Dòng đầu tiên chứa số nguyên dương \(n\) (\(n \leq 10^6\)); dòng tiếp theo, ghi \(n\) số nguyên \(A_i\) (\(0 \leq A_i \leq 10^9\)). Các số cách nhau 1 dấu cách.

Dữ liệu ra:

Ghi ra chi phí biến đổi tìm được.

Ví dụ:

Input

3
1 2 3

Output

5