Cho dãy số nguyên ~a_1, a_2, \dots, 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ế hai 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~.

Input

• Dòng đầu tiên chứa số nguyên ~n\ (1 \le n \le 10^6)~,
• Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa số nguyên ~a_i\ (0 \le a_i \le 10^9)~.

Output

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

Example

Input

3
1
2
3

Output

5