Harry and the Books

All submissions for this problem are available.
Harry and Ron once again got caught by Finch doing something mischievious. As a punishment, they are asked to arrange books in the library. Now since its a magical world the library has 1000000 floors. Each book has the floor number written on it where it is to be kept. Your are given a list of integers BOOK[] containing the floor numbers where the book is to be kept in order. Each book will either be placed by Harry or Ron. Once again since its a magical world both Harry and Ron have access to the books at the same time and in any floor but they must place the book themselves. The books must be placed in the order they are in the array that is BOOK[i] must be placed before BOOK[j] if i < j.
Changing floor is difficult and exhaustive . The difficulty for Ron and Harry can be computed by summing up the differences between consecutive FLOORS they visit. For example, the difficulty of the sequence 10,9,11,16 for Harry is mod(910)+mod(119)+mod(1611).
The total difficult of the entire work can be calculated as the difficulty for Harry plus Difficulty of Ron.
Print the smallest possible difficulty for doing the complete work.
Input
The first line of input contains an Integer T (number of test cases).
Then each of the next T lines contains an integer N (total number of BOOKS to be placed) and then N integers(BOOK[] ARRAY) separated by space in the same line.
Output
For each Test Case Print the smallest possible difficulty for doing the complete work.
Constraints
 1 ≤ T ≤ 15
 1 ≤ N ≤ 2000
Example
Input: 2 5 1 5 6 2 1 6 5 4 5 4 5 4 Output: 3 0
Explanation
In the first case Harry works with the sequence of BOOKS {1,2,1} and Ron works with {5,6}. Hence the difficulty for HARRY is 2 and the difficulty for RON is 1.
Author:  jammeron 
Tags  jammeron 
Date Added:  9042015 
Time Limit:  5 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CAML, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 