Nim, Rhezo and Subarrays

★★★★★

4.3

15 votes

Medium

Details

Problem

Nim likes to solve hard problems. Today he made a hard problem for Rhezo to solve. The problem is too hard for him and he needs your help to solve it, please help him!

Given an array $a_1$ , $a_2$ , $a_3$ ..... $a_n$ all elements of which are initialised to 0 .

Convert this array into another array $b_1$ , $b_2$ ,.... $b_n$ with minimum number of operations .

Operations can be of following two type:

(1) Add 1 to each element of the sub array [l,r] where l and r denote position of elements in the array ( $1 \le l \le r \le n$ ).

(2) Subtract 1 from each element of the sub array [l,r] where l and r denotes position of elements in the array ( $1 \le l \le r \le n$ ).

Input

The first line of the input consists of a single integer n ( $1 \le n \le 100000$ ). Second line of the input consists of n space separated integers $b_1$ , $b_2$ .... $b_n$ ( $-10^9 \le b_i \le 10^9$ ) .

Output

Print the result .

Note : Initially all elements of array a are initialised to 0 .

Sample Input

5
1 2 3 4 5

Sample Output

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

$For$ $sample$ $test$ $case$ :- Initially array A is : 0 0 0 0 0

op1 -> Add 1 to all elements in the subarray [1,5] .

Now array A is : 1 1 1 1 1

op2 -> Add 1 to all elements in the subarray[2,5] .

Now array A is : 1 2 2 2 2

op3 -> Add 1 to all elements in the subarray [3,5] .

Now array A is : 1 2 3 3 3

op4 -> Add 1 to all elements in the subarray[4,5] .

Now array A is : 1 2 3 4 4

op5 -> Add 1 to all elements in the subarray [5,5] .

Now array A is : 1 2 3 4 5

So in total their are 5 operations required .