Cho một dãy ~N~ viên gạch lần lượt có độ cách nhiệt là các số ~a_{1}~ ...~a_{N}~. Nếu xếp lần lượt các viên gạch theo trình tự đó thì độ cách nhiệt cả khối là ~a_{1} + a_{2} + \dots + a_{N} + max(0, a_{2} - a_{1}) + max(0, a_{3} - a_{2}) + \dots + max(0, a_{N} - a_{N - 1})~. Nhiệm vụ của bạn là tìm cách xếp sao cho độ cách nhiệt của cả khối là lớn nhất có thể.

Input

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

Output

Ghi trên một dòng kết quả cần tìm.

Sample Input

4
5
4
1
7

Sample Output

24