This 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 (al, r) (a continuous sequence of elements (a_l, a_{l + 1}, \dots, a_r)) for which the value of the expression (\text{med}(al, r) - \min(al, 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 (a2, 5 = 4, 1, 5, 3). In sorted form, it looks like (1, 3, 4, 5). (\text{med}(a2, 5) = 4), since (\left\lceil \frac{4 + 1}{2} \right\rceil =) the third element in the sorted subarray is (4); (\min(a2, 5) = 1), since the minimum element is (1). In this example, the value (\text{med} - \min = 4 - 1 = 3). 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 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). For each test case, output one integer — the maximum possible value of (\text{med} - \min) among all subarrays of the array. In the first example, consider the array: (a=3,\ 2,\ 5,\ 3,\ 1) you can choose the subarray (a2,\ 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,