Cho ~N~ bình chứa nước lần lượt có thể tích là các số ~a_1.. a_N~. Khi xếp các bình theo một dãy thì sẽ tạo thành 1 khối. Nếu xếp lần lượt các bình chứa nước theo trình tự đó thì thể tích cả khối là ~a_1 + a_2 + ... + a_N + max(0, a_2 - a_1) + max(0, a_3 - a_2) + ... + max(0,a_N - a_{N - 1}~. Nhiệm vụ của bạn là tìm cách xếp sao cho tổng thể tích chứa của cả khối là lớn nhất có thể.

Dữ liệu:

• Dòng đầu ghi số nguyên dương ~N~ (~0 < n ≤ 10^5~).
• ~N~ dòng sau mỗi dòng ghi một số ~a_i~ ( ~1 ≤ i ≤ N và 1 ≤ a_i ≤ 10000~).

Kết quả:

• Ghi trên một dòng kết quả là thể tích lớn nhất tìm được.

Ví dụ

Input

4
5 4 1 7

Output

24