Suit Up

Mike works at a law firm and his boss Harvey has assigned him N new cases, each having its own benefit value. Harvey has asked him to divide the consecutive cases into groups such that the total benefit value of all the groups is the maximum possible.

The benefit value of a group is determined by the difference between the maximum and minimum individual benefit values of the cases in that group. Harvey knows that this will be an easy task for Mike, so he has asked Mike to keep just one thing in mind. If a group consists of a single case, its value will be considered as zero.

You are given an integer N$,$ representing the number of cases, and an integer array A$,$ representing the benefit value of the cases. Your task is to help Mike find and return an integer value representing the maximum benefit value from all the groups.

Input Specification

input$1$: An integer value N$,$ representing the number of cases.

input$2$: An integer array A$,$ representing the benefit value of the cases.

Example $1$

input $1$: $5$

input $2$: $\{1,3,2,4,5\}$

Output: $5$

Explanation:

There are $5$ cases, and we get the maximum benefit value of the cases in the following order.

Group $1$: $(1,3),$ Maximum benefit value $=3-1-2$

Group $2$: $(2,4,5),$ Maximum benefit value $=5-2-3.$

Total benefit value $=2+3=5.$ Therefore, $5$ is returned as the output.

Example $2$

input$1$: $1$

input$2$: $\{5\}$

Output: $0$

Explanation:

There is $1$ case, and we get the maximum benefit value of the cases in the following order.

Group $1$: $\{5\}$ Total benefit value $=0($Single case$).$

Therefore, $0$ is returned as the output.

class UserMainCode $\{$

public:

static int maximumBenefit$($int input$1,$ std::vector input$2)\{$

$//$ Write code here

$//...$

return $0$; $//$ Replace with the actual result

$\}$

$\}$;