这是问题的困难版本。版本之间的区别在于,在此版本中 $$$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 =$$$ 已排序子数组中的第三个元素是 $$$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$$$ 的最大可能值。
示例
输入复制
553 2 5 3 144 1 1 376 1 3 4 6 2 744 2 3 151 2 3 4 5
输出复制
3 3 5 2 2
注意
在第一个示例中,考虑数组:$$$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$$$。
- 子数组的最小元素:$$$\min = 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$$$。
- 子数组的最小元素:$$$\min = 1$$$。
因此,$$$\text{med} - \min = 4 - 1 = 3$$$。
可以证明这两个子数组都是最优的,并且产生表达式 $$$\text{med} - \min$$$ 的最大值。