CF2128E2 Submedians (Hard Version)

This is the hard version of the problem. The only difference is that in this version, you are asked to find a subarray for all submedians. 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] $ . Find all submedians and for each of them, find 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 your answer in the following format. On the first line, output $ c $ , the number of submedians. On the $ i $ -th of the following $ c $ lines, output three integers $ v_i $ , $ l_i $ , and $ r_i $ such that - $ r_i - l_i + 1 \geq k $ , and - $ v_i $ is one of the medians of the subarray $ [a_{l_i}, \ldots, a_{r_i}] $ . Each submedian should be reported exactly once, that is, integers $ v_1, \ldots, v_c $ must be pairwise distinct. The order in which they are reported does not matter. 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 = 4, r = 5) $ : $ [2, 1] $ whose medians are $ 1 $ and $ 2 $ , - $ (l = 1, r = 5) $ : whose only median is $ 2 $ , - $ (l = 3, r = 4) $ : $ [3, 2] $ whose medians are $ 2 $ and $ 3 $ . All of these subarrays are indeed of length at least $ 2 $ . Note that it can be proven that no subarray of length at least $ 2 $ admits $ 4 $ or $ 5 $ as a median.