596B.md (1537B)
1 Source: https://codeforces.com/problemset/problem/596/B 2 3 B. Wilbur and Array 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Wilbur the pig is tinkering with arrays again. He has the array *a*1, *a*2, ..., *a**n* initially consisting of *n* zeros. At one step, he can choose any index *i* and either add 1 to all elements *a**i*, *a**i* + 1, ... , *a**n* or subtract 1 from all elements *a**i*, *a**i* + 1, ..., *a**n*. His goal is to end up with the array *b*1, *b*2, ..., *b**n*. 22 23 Of course, Wilbur wants to achieve this goal in the minimum number of steps and asks you to compute this value. 24 25 Input 26 27 The first line of the input contains a single integer *n* (1 ≤ *n* ≤ 200 000) — the length of the array *a**i*. Initially *a**i* = 0 for every position *i*, so this array is not given in the input. 28 29 The second line of the input contains *n* integers *b*1, *b*2, ..., *b**n* ( - 109 ≤ *b**i* ≤ 109). 30 31 Output 32 33 Print the minimum number of steps that Wilbur needs to make in order to achieve *a**i* = *b**i* for all *i*. 34 35 Examples 36 37 Input 38 39 ``` 40 5 41 1 2 3 4 5 42 ``` 43 44 Output 45 46 ``` 47 5 48 ``` 49 50 Input 51 52 ``` 53 4 54 1 2 2 1 55 ``` 56 57 Output 58 59 ``` 60 3 61 ``` 62 63 Note 64 65 In the first sample, Wilbur may successively choose indices 1, 2, 3, 4, and 5, and add 1 to corresponding suffixes. 66 67 In the second sample, Wilbur first chooses indices 1 and 2 and adds 1 to corresponding suffixes, then he chooses index 4 and subtract 1.