E1. Submedians (Easy Version)
binary search; data structures; dp; greedy; math
This is the easy version of the problem. The only difference is that in this version, you are asked to find a subarray only for the maximum submedian.You can make hacks only if both versions of the problem are solved.An integer \(v\) is a median of an array \(b\) of length \(m\) if and only if: \(v\) is greater than or equal to at least \(\lceil \frac{m}{2} \rceil\) elements of the array, and \(v\) is less than or equal to at least \(\lceil \frac{m}{2} \rceil\) elements of the array. For instance: the only median of \([9, 3, 7]\) is \(7\), the medians of \([5, 3, 7, 9]\) are \(5\), \(6\), and \(7\), and the only median of \([2, 2, 2]\) is \(2\). You're given an integer \(k\) and an array \(a_1, \ldots, a_n\) of integers between \(1\) and \(n\).An integer \(v\) from \(1\) to \(n\) is said to be a submedian if there exists at least one pair of indices \((l, r)\) such that \(1 \leq l \leq r \leq n\), \(r - l + 1 \geq k\), \(v\) is a median of the subarray \([a_l, \ldots, a_r]\). It can be proven that there always exists at least one submedian. Find the maximum submedian \(v_\max\) and any corresponding pair of indices \((l, r)\).
Each test contains multiple test cases. The first line contains the number of test cases \(t\) (\(1 \le t \le 50\,000\)). The description of the test cases follows. The first line of each test case contains two integers \(n\) and \(k\) (\(1 \leq k \leq n \leq 300\,000\)).The second line of each test case contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq n\)).It is guaranteed that the sum of \(n\) over all test cases doesn't exceed \(300\,000\).
For each test case, output three integers \(v_\max\), \(l\), and \(r\) — the maximum submedian \(v_\max\) and the bounds of a subarray of length at least \(k\) (\(r - l + 1 \geq k\)) such that \(v_\max\) is one of its medians.If there are many solutions, you can print any of them.
In the first test case, the subarrays of length at least \(k = 3\) are \((l = 1, r = 3)\): \([4, 1, 2]\) whose only median is \(2\), \((l = 2, r = 4)\): \([1, 2, 4]\) whose only median is \(2\), and \((l = 1, r = 4)\): \([4, 1, 2, 4]\) whose medians are \(2\), \(3\), and \(4\). In the second test case, one possible output is \((l = 3, r = 4)\) whose medians are \(2\) and \(3\).Note that it can be proven that no subarray of length at least \(2\) admits \(4\) or \(5\) as a median.