JDCC '17 Contest 2 S2 - Cookie Platters

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type

Marcus is so excited for Christmas, that he decided to make N cookie platters for Santa!

To do so, he took N ovens, all of which are lined up in a row, and decided to set the n^{th} oven to a temperature of b_n degrees (all of the ovens are initially 0 degrees).

Marcus decides to set the temperatures in a weird way. If he increases the temperature of an oven by x, he must also increase the temperature of all ovens to the right by x.

Similarly, if he reduces the temperature by x, he must also reduce the temperature of all ovens to the right by x (it is possible to set an oven to a negative temperature).

He wants to finish this task before Santa arrives, and he asks you to figure out the minimum number of steps it takes him to finish setting all ovens to the right temperature.

Input

The first line contains an integer N (1 \le N \le 10^5), signifying the number of ovens.

The next line has N integers b_n (0 \le b_n \le 10^4), representing the temperature he wants the n^{th} oven to have.

Output

Output one integer, the minimum number of steps it takes him to set each oven to the right temperature.

Sample Input

5
1 4 3 2 5

Sample Output

5

Explanation for Sample Input

Marcus initially has 5 ovens, each at temperature 0. He then performs the following steps:

  • Increase the temperature of the 1^{st} oven by 1 (1 1 1 1 1)
  • Increase the temperature of the 5^{th} oven by 3 (1 1 1 1 4)
  • Increase the temperature of the 2^{nd} oven by 3 (1 4 4 4 7)
  • Decrease the temperature of the 4^{th} oven by 1 (1 4 4 3 6)
  • Decrease the temperature of the 3^{rd} oven by 1 (1 4 3 2 5)

Comments


  • -1
    MstrPikachu  commented on Nov. 12, 2018, 11:26 p.m.

    Why isn't the temperature measured in Kelvin