404406: GYM101498 K Two Subarrays

In this problem, subarray is defined as non-empty sequence of consecutive elements of an array.

The strength of an array Z of size K is computed as follows:

Given an array A of size N, find the maximum possible absolute difference between the strengths of two non-intersecting subarrays of A.

Two subarrays intersect if they have common indices.

The first line of the input contains an integer T (1 ≤ T ≤ 100), where T is the number of test cases.

Each case contains two lines. The first line contains an integer N (2 ≤ N ≤ 10⁵), the size of the array A.

The second line contains N space-separated integers representing the elements of the array A ( - 10⁹ ≤ A_i ≤ 10⁹).

For each test case, print the maximum possible absolute difference on a single line.

3
4
0 1 2 100
6
-9 1 -3 5 4 2
5
4 3 2 3 4

101
22
5