CF2126G2.Big Wins! (hard version)

这是该问题的困难版本。不同之处在于本版本中 $a_i \leq n$。

给定一个长度为 $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 n$），表示数组的元素。

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

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

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

• 子数组长度为 $2$。
• 中位数为排序后第 $\left\lceil \dfrac{3}{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 \dfrac{3}{2} \right\rceil = 2$ 个元素。排序后为 $[1,\ 4]$，$\text{med} = 4$。
• 子数组的最小元素为 $1$。

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

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

由 ChatGPT 4.1 翻译