CF2149G Buratsuta 3

In the ruthless world of Blue Lock, Buratsuta 3 is a trio selected to overthrow the reigning champions and lead the Japan U-20 team to glory. Sae Itoshi has already secured his place as the first participant; the remaining two spots will be contested in the tough Side-B selection. To test the strategic abilities of the candidates, Buratsuta has posed the following challenge: You are given an array of $ n $ integers called "performance records" and $ q $ queries. Each query specifies a subarray $ [l, r] $ . In this subarray, find all record values that occur strictly more than $ \lfloor\tfrac{r - l + 1}{3}\rfloor $ times.

Each test consists of several test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The following describes the test cases. The first line of each test case contains two integers $ n $ and $ q $ $ (1 \le n, q \le 2\cdot10^5) $ — the number of records and the number of queries. The second line of each test case contains $ n $ integers $ a_1, a_2, \dots, a_n $ $ (1 \le a_i \le 10^9) $ — the performance records. Each of the following $ q $ lines contains two integers $ l $ and $ r $ $ (1 \le l \le r \le n) $ — the boundaries of the query. It is guaranteed that the sum of $ n $ and sum of $ q $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each query, output in one line all record values (in sorted order) that occur strictly more than $ \lfloor\tfrac{r - l + 1}{3}\rfloor $ times in the segment $ [l, r] $ . If there are no such values, output $ -1 $ .

In the second test case, the array is $ a=[1,1,2,3] $ and there are two queries: - Query $ (l,r)=(1,4) $ : The length of the segment $ len=r-l+1=4 $ , the threshold $ \bigl\lfloor \frac{len}{3}\bigr\rfloor+1 = 2 $ . Occurrences of numbers: $ 1\!\to\!2 $ , $ 2\!\to\!1 $ , $ 3\!\to\!1 $ . Only the number $ 1 $ occurs at least $ 2 $ times, so the answer is: $ 1 $ . - Query $ (l,r)=(2,3) $ : The length of the segment $ len=2 $ , the threshold $ \bigl\lfloor \frac{len}{3}\bigr\rfloor+1 = 1 $ . Numbers $ 1 $ and $ 2 $ occur once each, so the answer is: $ 1 \; 2 $ . In the fourth test case, the array is $ a=[4,4,4,5,5,5,6,6] $ and there are two queries: - Query $ (l,r)=(1,8) $ : The length of the segment $ len = 8 $ , the threshold $ \bigl\lfloor \dfrac{len}{3} \bigr\rfloor + 1 = 3 $ . Occurrences of numbers: $ 4 \!\to\! 3 $ , $ 5 \!\to\! 3 $ , $ 6 \!\to\! 2 $ . Only the numbers $ 4 $ and $ 5 $ occur at least $ 3 $ times, so the answer is: $ 4 \; 5 $ . - Query $ (l,r)=(3,6) $ : The length of the segment $ len = 4 $ , the threshold $ \bigl\lfloor \dfrac{len}{3} \bigr\rfloor + 1 = 2 $ . Occurrences of numbers: $ 4 \!\to\! 1 $ , $ 5 \!\to\! 3 $ . Only the number $ 5 $ occurs at least $ 2 $ times, so the answer is: $ 5 $ .