CF1630B Range and Partition

Given an array $ a $ of $ n $ integers, find a range of values $ [x, y] $ ( $ x \le y $ ), and split $ a $ into exactly $ k $ ( $ 1 \le k \le n $ ) subarrays in such a way that: - Each subarray is formed by several continuous elements of $ a $ , that is, it is equal to $ a_l, a_{l+1}, \ldots, a_r $ for some $ l $ and $ r $ ( $ 1 \leq l \leq r \leq n $ ). - Each element from $ a $ belongs to exactly one subarray. - In each subarray the number of elements inside the range $ [x, y] $ (inclusive) is strictly greater than the number of elements outside the range. An element with index $ i $ is inside the range $ [x, y] $ if and only if $ x \le a_i \le y $ . Print any solution that minimizes $ y - x $ .

The input consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 3 \cdot 10^4 $ ) — the number of test cases. Description of the test cases follows. The first line of each test case contains two integers $ n $ and $ k $ ( $ 1 \le k \le n \le 2 \cdot 10^5 $ ) — the length of the array $ a $ and the number of subarrays required in the partition. The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le n $ ) where $ a_i $ is the $ i $ -th element of the array. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot10^5 $ .

For each test case, print $ k+1 $ lines. In the first line, print $ x $ and $ y $ — the limits of the found range. Then print $ k $ lines, the $ i $ -th should contain $ l_i $ and $ r_i $ ( $ 1\leq l_i \leq r_i \leq n $ ) — the limits of the $ i $ -th subarray. You can print the subarrays in any order.

In the first test, there should be only one subarray, which must be equal to the whole array. There are $ 2 $ elements inside the range $ [1, 2] $ and $ 0 $ elements outside, if the chosen range is $ [1, 1] $ , there will be $ 1 $ element inside ( $ a_1 $ ) and $ 1 $ element outside ( $ a_2 $ ), and the answer will be invalid. In the second test, it is possible to choose the range $ [2, 2] $ , and split the array in subarrays $ (1, 3) $ and $ (4, 4) $ , in subarray $ (1, 3) $ there are $ 2 $ elements inside the range ( $ a_2 $ and $ a_3 $ ) and $ 1 $ element outside ( $ a_1 $ ), in subarray $ (4, 4) $ there is only $ 1 $ element ( $ a_4 $ ), and it is inside the range. In the third test, it is possible to choose the range $ [5, 5] $ , and split the array in subarrays $ (1, 4) $ , $ (5, 7) $ and $ (8, 11) $ , in the subarray $ (1, 4) $ there are $ 3 $ elements inside the range and $ 1 $ element outside, in the subarray $ (5, 7) $ there are $ 2 $ elements inside and $ 1 $ element outside and in the subarray $ (8, 11) $ there are $ 3 $ elements inside and $ 1 $ element outside.