G1. Big Wins! (easy version)
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Example
Input
5
5
3 2 5 3 1
4
4 1 1 3
7
6 1 3 4 6 2 7
4
4 2 3 1
5
1 2 3 4 5
Output
3
3
5
2
2
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$$$.