CF2126G2 Big Wins! (hard version)

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 $ 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 $ .

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 $ 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 $ .