Zulu is good in maths. He loves to play with numbers. One day while browsing through a book, he encountered a nice problem. In the problem, he was given an array A of N numbers.
For each index i in the array we define two quantities. Let r be the maximum index such that r>=i and sub-array from i to r (inclusive) is either non-decreasing or non-increasing. Similarly, let l be the minimum index such that l<=i and sub-array from l to i (inclusive) is either non-decreasing or non-increasing. Now, we define points of an index i to be equal to max(|Ai−Al|,|Ai−Ar|). Note that l and r can be different for each index i.
The task of the problem is to find the index of the array A which have the maximum points.
Since the problem seems a bit harder, Zulu is struck. Can you solve this problem for Zulu?
Input:
In the first line of input, TEST will be given which is the number of test cases. For each of the test case, a single integer N will be given in the first line. In the second line, N space separated integers will be provided.
Output:
For each of the test cases, output the points of the index which have maximum points in the array in a separate line.
Constraint:
-
1≤TEST≤5
-
1≤N≤2∗105
-
−2∗109≤A[i]≤2∗109
In the first test case, M will be equal to |1−2|=1.
In the second test case: For the first index, L=−4, R=1. For the second index, L=−4, R=0. For the third index, L=1, R=0. So the maximum value of M is |1−(−4)|=5.
