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 ~10~ 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.
The first line of input contains an integer ~N~ ~(1 \le N \le 10^5)~, the number of areas on her commute.
The next line contains ~N~ space-separated integers, labeled ~v_1, v_2, \ldots, v_N~, where ~v_i~ is the volume of the area at location ~i~ in decibels. It is guaranteed that ~10 \le v_i \le 10^4~.
Output the minimum total decibel change.
Subtask 1 [12%]
~N \le 4~
Subtask 2 [17%]
~N \le 200~
Subtask 3 [25%]
~N \le 2000~
Subtask 4 [46%]
No further constraints.
4 73 11 58 48
Morgan can start off with her volume at ~63~ decibels and take a shortcut to skip out on the second area. Then, she can keep her volume at ~63~ decibels for the third area, and finally change it to ~58~ at the fourth area. ~63~ dB to ~63~ dB to ~58~ dB is a total change of ~5~ decibels.