Maximizing the Sum of Peak-Valley Differences

You are given an array of integers where each element represents the height of a hill. Your task is to select a pivot that splits the array into two non-overlapping contiguous subarrays. For each subarray, compute the difference between the maximum height (peak) and the minimum height (valley). Formally, for a subarray, if \(\text{max}\) and \(\text{min}\) denote its maximum and minimum values respectively, the difference is given by \(\text{diff} = \text{max} - \text{min}\). Your objective is to choose a split so that the sum of the differences of the two subarrays is maximized.

Note: The split must be such that both subarrays are non-empty. That is, if the original array has n elements, then the left subarray can be taken from indices 0 to i and the right subarray from indices i+1 to n-1 for some index \(0 \le i < n-1\).

Example:

Input:
3
5
1 2 6 4 5
6
10 8 2 5 7 6
4
1 3 1 3
Output:
6
10
4

</p>

inputFormat

The first line of the input contains a single integer, T, representing the number of test cases. Each test case is described as follows:

• The first line of a test case contains an integer n, the number of hills.
• The second line contains n space-separated integers representing the heights of the hills.

outputFormat

For each test case, output a single line containing a single integer which is the maximum possible sum of the differences between the highest and lowest hill in two non-overlapping contiguous subarrays.

## sample

3
5
1 2 6 4 5
6
10 8 2 5 7 6
4
1 3 1 3

6
10
4

</p>