Đề bài

Cho dãy số nguyên ~a_1, a_2, \dots, a_n~ (~0 \leq a_i \leq 10^9~, ~1 \leq n \leq 10^6~). 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 ~1~.

Input

• Dòng đầu tiên chứa số nguyên ~n~.
• Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa số nguyên ~a_i~.

Output

• Đưa ra một số nguyên — chi phí biến đổi tìm được.

Ví dụ

Sample Input

3
1
2
3

Sample Output

5

Giới hạn

• Thời gian: 1.0s
• Bộ nhớ: 256M