Cách nhiệt

Xem PDF

Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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+⋯+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 độ 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≤ 10^5\)).
  • \(N\) dòng sau mỗi dòng ghi một số \(a_i\) (\(1≤ i≤ N\) và \(1≤ a_i≤ 10000\)).

Output

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

Example

Test 1

Input
4
5
4
1
7 
Output
24

Bình luận