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 \le 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~ và ~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_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 vào

• Dòng đầu tiêu chứa duy nhất một số nguyên dương ~N~ ~(0 \le N \le 10^5)~.
• ~N~ dòng tiếp theo mỗi dòng chứa một số nguyên ~a_i~ (~1 \le i \le N~ và ~1 \le a_i \le 10000~).

Dữ liệu ra

Một dòng duy nhất chứa một số nguyên là độ cách nhiệt lớn nhất của cả khối.

Ví dụ

Dữ liệu vào

4
5
4
1
7

Dữ liệu ra

24