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.
Subtasks
Subtask 1 [12%]
Subtask 2 [17%]
Subtask 3 [25%]
Subtask 4 [46%]
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.
Comments