Trò chơi thứ ba của lớp 9A là trò chơi xếp các khối hình vuông. Cô chủ nhiệm cho mỗi tổ ~N~ ~(0 < N \le 10^5)~ khối hình vuông, các khối hình vuông của tổ 1 giống các khối hình vuông của tổ 2. Trên mỗi khối hình vuông có một số nguyên ~a_i~ ~(1 \le i \le N;\ 1 \le a_i \le 10000)~ thể hiện khả năng cách nhiệt của hình vuông đó. Nếu xếp lần lượt các khối hình vuông theo trình tự ~a_1, a_2, ..., a_N~ thì độ cách nhiệt 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})~.

Yêu cầu

Bạn hãy giúp An xếp các khối hình vuông sao cho độ cách nhiệt của cả khối là lớn nhất.

Dữ liệu đầu vào

Gồm ~N + 1~ dòng:

• Dòng đầu tiên gồm số ~N~.
• ~N~ dòng tiếp theo, dòng thứ ~i~ gồm giá trị ~a_i~ ~(1 \le i \le N)~.

Dữ liệu đầu ra

Gồm một dòng duy nhất chứa kết quả của bài.

Ví dụ

Ví dụ 1

INPUT

4
5
4
1
7

OUTPUT

24