Longest Strike

题意翻译

给你一个长度为 $n$ 的序列 $a$ 和一个整数 $k$，你要求一个区间 $[l,r]$ 满足： - 对于任何整数 $x∈[l,r]$，$x$ 在 $a$ 中的出现次数不少于 $k$ 次。 - 最大化 $r-l$。 无解输出 `-1`。 例如，$a=[11,11,12,13,13,14,14],k=2$ 时： - $l=12,r=14$ 不满足条件，因为 $12$ 只出现了 $1$ 次。 - $l=13,r=14$ 满足条件，因为 $13$ 出现了 $2$ 次，$14$ 出现了 $2$ 次。 - $l=11,r=11$ 满足条件，因为 $11$ 出现了 $2$ 次。 满足条件且 $r-l$ 最大的区间是 $l=13,r=14$。

题目描述

Given an array $ a $ of length $ n $ and an integer $ k $ , you are tasked to find any two numbers $ l $ and $ r $ ( $ l \leq r $ ) such that: - For each $ x $ $ (l \leq x \leq r) $ , $ x $ appears in $ a $ at least $ k $ times (i.e. $ k $ or more array elements are equal to $ x $ ). - The value $ r-l $ is maximized. If no numbers satisfy the conditions, output -1. For example, if $ a=[11, 11, 12, 13, 13, 14, 14] $ and $ k=2 $ , then: - for $ l=12 $ , $ r=14 $ the first condition fails because $ 12 $ does not appear at least $ k=2 $ times. - for $ l=13 $ , $ r=14 $ the first condition holds, because $ 13 $ occurs at least $ k=2 $ times in $ a $ and $ 14 $ occurs at least $ k=2 $ times in $ a $ . - for $ l=11 $ , $ r=11 $ the first condition holds, because $ 11 $ occurs at least $ k=2 $ times in $ a $ . A pair of $ l $ and $ r $ for which the first condition holds and $ r-l $ is maximal is $ l = 13 $ , $ r = 14 $ .

输入输出格式

输入格式

# The first line of the input contains a single integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains the integers $ n $ and $ k $ ( $ 1 \le n \le 2 \cdot 10^5 $ , $ 1 \leq k \leq n $ ) — the length of the array $ a $ and the minimum amount of times each number in the range $ [l, r] $ should appear respectively. Then a single line follows, containing $ n $ integers describing the array $ a $ ( $ 1 \leq a_i \leq 10^9 $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case output $ 2 $ numbers, $ l $ and $ r $ that satisfy the conditions, or "-1" if no numbers satisfy the conditions. If multiple answers exist, you can output any.

输入输出样例

输入样例 #1

4
7 2
11 11 12 13 13 14 14
5 1
6 3 5 2 1
6 4
4 3 4 3 3 4
14 2
1 1 2 2 2 3 3 3 3 4 4 4 4 4

输出样例 #1

13 14
1 3
-1
1 4