ECOO '21 Practice P4 - Noisy Commute

View as PDF

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

Note this problem was originally intended for the cancelled 2020 Girls Invitational Competition.

Morgan likes to listen to music on her commute to school. However, her commute is very noisy, and different areas have different noise levels. In order to listen to her music properly, she must adjust the volume of her music to be at most decibels higher or lower than the surrounding volume.

For the best music listening experience, she wants to be able to change the volume as little as possible, or else the volume change will be too jarring for her. She can take one shortcut at any point, cutting out one noisy area of her commute.

Input Specification

The first line of input contains an integer , the number of areas on her commute.

The next line contains space-separated integers, labeled , where is the volume of the area at location in decibels. It is guaranteed that .

Output Specification

Output the minimum total decibel change.

No further constraints.

Sample Input

4
73 11 58 48

Sample Output

5

Explanation

Morgan can start off with her volume at decibels and take a shortcut to skip out on the second area. Then, she can keep her volume at decibels for the third area, and finally change it to at the fourth area. dB to dB to dB is a total change of decibels.