G2. Big Wins! (hard version)time limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThis is the hard version of the problem. The difference between the versions is that in this version $$$a_i \leq n$$$.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}$$$ is the median of the subarray, that is, the element at position $$$\left\lceil \frac{k + 1}{2} \right\rceil$$$ after sorting the subarray, where $$$k$$$ is its length; $$$\min$$$ is 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$$$.InputThe 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 n$$$) — the elements of the array.It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.OutputFor each test case, output one integer — the maximum possible value of $$$\text{med} - \min$$$ among all subarrays of the array.ExampleInput553 2 5 3 144 1 1 376 1 3 4 6 2 744 2 3 151 2 3 4 5Output3
3
5
2
2
NoteIn the first example, consider the array: $$$a=[3,\ 2,\ 5,\ 3,\ 1]$$$ you can choose the subarray $$$a[2,\ 3]$$$, that is, 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]$$$, that is, 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$$$.