# How to solve this problem?

You are given an integer array A of size N. You can divide this array A into any number of contiguous subarrays (possibly zero). The degree of freedom for a subarray is the absolute difference between the maximum and minimum element in a subarray.

Task: Print the maximum sum of the degree of freedom of all subarrays that can be achieved by dividing A into some possible arrangement of contiguous subarrays

Note

•A subarray of an array is a sequence obtained by removing zero or more elements from either both the front and back of the array. The subarrays of array [1,5,2] are (, [1,5] [1,5,2], , [5,2],] and [1,2] cannot be called a subarray of [1,5,2] because it cannot be obtained by removing elements from front or back of [1,5,2] •Contiguous subarray means that all the subarrays should have consecutive indexes. An array [1,2,3] can be divided into contiguous subarray as [1,2,3]or [1,2], or [2,3]

Example

Assumptions N=5 A = [1,2,1,0,5]

Approach

Optimally we can divide A into three consecutive subarrays [1,2],  and [0,5]. The degree of freedoms of the subarrays is O and 5 respectively. Thus the maximum sum of the degree of freedom of all subarrays is 6.

A Represents an integer array denoting elements of array A

Test Cases: N=4; A=[1,4,2,3]; Output=4
N=5; A=[1,2,3,2,1]; Output=3