Cách nhiệt

View as PDF

Submit solution


Points: 0.09 (partial)
Time limit: 0.38s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
POI 2001/2002
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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

Comments

Please read the guidelines before commenting.


There are no comments at the moment.