CF2126G1.Big Wins! (easy version)

这是该问题的简单版本。不同之处在于本版本中 $a_i \leq \min(n,100)$。

给定一个长度为 $n$ 的整数数组 $a_1, a_2, \dots, a_n$。

你的任务是找到一个子数组 $a[l, r]$（即一段连续的元素 $a_l, a_{l + 1}, \dots, a_r$），使得表达式 $\text{med}(a[l, r]) - \min(a[l, r])$ 的值最大。

其中：

• $\text{med}$ 表示子数组的中位数，即将子数组排序后位于第 $\left\lceil \frac{k + 1}{2} \right\rceil$ 个位置的元素，其中 $k$ 是子数组的长度；
• $\min$ 表示该子数组中的最小元素。

例如，考虑数组 $a=[1, 4, 1, 5, 3, 3]$，选择子数组 $a[2, 5] = [4, 1, 5, 3]$。排序后为 $[1, 3, 4, 5]$。

• $\text{med}(a[2, 5]) = 4$，因为 $\left\lceil \frac{4 + 1}{2} \right\rceil = 3$，排序后第 3 个元素是 $4$；
• $\min(a[2, 5]) = 1$，因为最小元素是 $1$。

在本例中，$\text{med} - \min = 4 - 1 = 3$。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示数组的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq \min(n, 100)$），表示数组的元素。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示在所有子数组中 $\text{med} - \min$ 的最大可能值。

在第一个样例中，考虑数组 $a=[3, 2, 5, 3, 1]$，你可以选择子数组 $a[2, 3]$，即 $[2, 5]$。

• 子数组长度为 $2$。
• 中位数是排序后第 $\left\lceil \frac{2 + 1}{2} \right\rceil = 2$ 个元素。排序后为 $[2, 5]$，$\text{med} = 5$。
• 子数组的最小元素为 $2$。

因此，$\text{med} - \min = 5 - 2 = 3$，这是最大答案。

在第二个样例中，数组为 $a=[4, 1, 1, 3]$，你可以选择子数组 $a[1, 2]$，即 $[4, 1]$。

• 子数组长度为 $2$。
• 中位数是排序后第 $\left\lceil \frac{2 + 1}{2} \right\rceil = 2$ 个元素。排序后为 $[1, 4]$，$\text{med} = 4$。
• 子数组的最小元素为 $1$。

因此，$\text{med} - \min = 4 - 1 = 3$。

可以证明，这两个子数组都是最优的，并且都能得到表达式 $\text{med} - \min$ 的最大值。

由 ChatGPT 4.1 翻译