Các robot đang tiến hành hàn các tấm vách cách nhiệt được sử dụng trong các công trình xây dựng, mỗi tấm vách cách nhiệt được tạo thành từ $N$ lớp cách nhiệt được sắp xếp chồng lên nhau có hệ số cách nhiệt lần lượt là ~a_1,a_2,\dots,a_N~. Hệ số cách nhiệt của một tấm vách cách nhiệt bằng tổng hệ số cách nhiệt ban đầu của các lớp cách nhiệt cộng với độ chênh lệch giữa hai lớp cách nhiệt chồng lên nhau. Độ chênh lệch này được tính như sau:

• Nếu hệ số cách nhiệt của lớp cách nhiệt sau nhỏ hơn hoặc bằng lớp cách nhiệt trước đó thì độ chênh lệch giữa hai lớp cách nhiệt là ~0~ ~(a_{i+1}\le a_i)~

• Ngược lại nếu hệ số cách nhiệt của lớp cách nhiệt sau lớn hơn lớp cách nhiệt trước đó thì độ chênh lệch giữa hai lớp cách nhiệt này bằng hệ số cách nhiệt của lớp cách nhiệt sau trừ hệ số cách nhiệt của lớp cách nhiệt trước ~(a_{i+1}> a_i)~

Ví dụ:

• Hai lớp cách nhiệt được sắp xếp chồng lên nhau có hệ số cách nhiệt lần lượt là 5 và 4 thì tổng hệ số cách nhiệt là ~5+4+0=9~
• Hai lớp cách nhiệt được sắp xếp chồng lên nhau có hệ số cách nhiệt lần lượt là 4 và 5 thì tổng hệ số cách nhiệt là ~4+5+(5-4)=10~

Yêu cầu: Hãy lập trình giúp các robot sắp xếp các lớp cách nhiệt để hàn thành một tấm vách cách nhiệt sao cho hệ số cách nhiệt là lớn nhất có thể.

Dữ liệu vào

• Dòng đầu ghi số nguyên dương ~N~ ~(N\le10^5)~
• Dòng thứ hai ghi ~N~ số ~a_i~ ~(1 \le i \le N;1 \le a_i \le 10^5)~

Lưu ý: các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Kết quả ra

Xuất màn hình một số nguyên dương duy nhất là hệ số cách nhiệt lớn nhất cần tìm

Ví dụ

Dữ liệu

4
5 4 1 7

Kết quả

24

Giải thích

Tấm vách cách nhiệt gồm ~4~ lớp cách nhiệt được sắp xếp chồng lên nhau có hệ số cách nhiệt như sau: ~1, 5, 4, 7~ có tổng hệ số cách nhiệt lớn nhất: ~1+5+4+7+(5-1)+0+(7-4)=24~.