divyank-and-arrays

Divyank is in love with arrays.So while solving problems on arrays Divyank encountered the following problem :-

F(A) for an array A of size N is defined as sum of absolute difference between the consecutive numbers of the array.
e.g. for array A having elements as 3 5 1 F(A) will be (5-3)+(5-1) = 6.

Now you're given an array A and you have to distribute all the elements of this array into two empty arrays B and C in such a way that numbers in these arrays are in the same order as they were in array A.

e.g. if A is 1, 2, 3, 4, 5, 6 then one of the possible ways of distributing elements of A among B and C is as follows :-

B =  1, 2, 4, 5

C =  3, 6

Now you have to make the distribution in such a way that F(B)+F(C) is minimum.

Input :

First line of the input contains an integer T,number of test cases to follow.

First line of each test case is the total number of elements in the array A

Second line of each test case contains all the elements of the array as N space separated integers.

Output :

For each test case calculate the minimum value of F(B)+F(C).

Constraints :

1 ≤ T ≤ 15

1 ≤ N ≤ 2000

All elements in the array are between 1 and 10^6 both inclusive.

SAMPLE INPUT
1
5
2 5 7 8 9

SAMPLE OUTPUT
4

Explanation

There are many ways to distribute array A among B and C

Possibility 1

B : 2 8

C : 5 7 9

Here, F(B) + F(C) is 10

Possibility 2

B : 2

C : 5 7 8 9

Here, F(B) + F(C) is 4.

There are many other possibilities but the best one for the required task is as described in the Possibility 2

Source: hackerearth | Difficulty: MEDIUM
Tags: Dynamic programming


Solutions: