This is the easy version of the problem. The difference between the versions is that in this version $$$a_i \leq \min(n,100)$$$.

You are given an array of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$.

Your task is to find a subarray $$$a[l, r]$$$ (a continuous sequence of elements $$$a_l, a_{l + 1}, \dots, a_r$$$) for which the value of the expression $$$\text{med}(a[l, r]) - \min(a[l, r])$$$ is maximized.

Here:

$$$\text{med}$$$ — the median of the subarray, which is the element at position $$$\left\lceil \frac{k + 1}{2} \right\rceil$$$ after sorting the subarray, where $$$k$$$ is its length;
$$$\min$$$ — the minimum element of this subarray.

For example, consider the array $$$a=[1, 4, 1, 5, 3, 3]$$$ and choose the subarray $$$a[2, 5] = [4, 1, 5, 3]$$$. In sorted form, it looks like $$$[1, 3, 4, 5]$$$.

$$$\text{med}(a[2, 5]) = 4$$$, since $$$\left\lceil \frac{4 + 1}{2} \right\rceil = $$$ the third element in the sorted subarray is $$$4$$$;
$$$\min(a[2, 5]) = 1$$$, since the minimum element is $$$1$$$.

In this example, the value $$$\text{med} - \min = 4 - 1 = 3$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains one integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq \min(n, 100)$$$) — the elements of the array.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer — the maximum possible value of $$$\text{med} - \min$$$ among all subarrays of the array.

Note

In the first example, consider the array: $$$a=[3,\ 2,\ 5,\ 3,\ 1]$$$ you can choose the subarray $$$a[2,\ 3]$$$, which consists of the elements $$$[2,\ 5]$$$.

The length of the subarray is $$$2$$$.
The median is the element at position $$$\left\lceil \dfrac{3}{2} \right\rceil = 2$$$ in the sorted subarray. After sorting, we get $$$[2,\ 5]$$$, $$$\text{med} = 5$$$.
The minimum element of the subarray: $$$\min = 2$$$.

Therefore, $$$\text{med} - \min = 5 - 2 = 3$$$, which is the maximum answer.

In the second test, the array: $$$a=[4,\ 1,\ 1,\ 3]$$$ you can choose the subarray $$$a[1,\ 2]$$$, which consists of the elements $$$[4,\ 1]$$$.

The length of the subarray is $$$2$$$.
The median is the element at position $$$\left\lceil \dfrac{3}{2} \right\rceil = 2$$$ in the sorted subarray. After sorting, we get $$$[1,\ 4]$$$, $$$\text{med} = 4$$$.
The minimum element of the subarray: $$$\min = 1$$$.

Therefore, $$$\text{med} - \min = 4 - 1 = 3$$$.

It can be proven that both of these subarrays are optimal and yield the maximum value of the expression $$$\text{med} - \min$$$.

Big Wins! (easy version)

Examples