Cách nhiệt

Tác giả:

Dạng bài

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

Cho một dãy \(N\) viên gạch lần lượt có độ cách nhiệt là các số \(a_1 ... a_N\). Nếu xếp lần lượt các viên gạch theo trình tự đó thì độ cách nhiệt cả khối là \(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})\). Nhiệm vụ của bạn là tìm cách xếp sao cho độ cách nhiệt của cả khối là lớn nhất có thể.

Input

Dòng đầu ghi số nguyên dương \(N\) (\(0< n≤ 10^5\)).
\(N\) dòng sau mỗi dòng ghi một số \(a_i\) (\(1≤ i≤ N\) và \(1≤ a_i≤ 10000\)).

Output

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

Example

Test 1

Input

Output

Bình luận

2

longkold00 7:54 a.m. 12 Tháng 11, 2021 ← đã chỉnh sửa →

yamete:>

1 phản hồi