← 返回题目列表

Codeforces · 1676/F

F. 最长的罢工

中文机器翻译题面 查看原题

给定一个长度为 $$$n$$$ 的数组 $$$a$$$ 和一个整数 $$$k$$$,您的任务是找到任意两个数字 $$$l$$$ 和 $$$r$$$ ($$$l \leq r$$$),使得:

- 对于每个 $$$x$$$ $$$(l \leq x \leq r)$$$,$$$x$$$ 出现在 $$$a$$$ 中至少 $$$k$$$ 次(即 $$$k$$$ 或更多数组元素等于 $$$x$$$)。
- 值 $$$r-l$$$ 已最大化。

如果没有数字满足条件,则输出-1。

例如,如果 $$$a=[11, 11, 12, 13, 13, 14, 14]$$$ 且 $$$k=2$$$,则:

- 对于 $$$l=12$$$, $$$r=14$$$ 第一个条件失败,因为 $$$12$$$ 没有出现至少 $$$k=2$$$ 次。
- 对于 $$$l=13$$$,$$$r=14$$$,第一个条件成立,因为 $$$13$$$ 在 $$$a$$$ 中至少出现 $$$k=2$$$ 次,而 $$$14$$$ 在 $$$a$$$ 中至少出现 $$$k=2$$$ 次。
- 对于 $$$l=11$$$,$$$r=11$$$ 第一个条件成立,因为 $$$11$$$ 在 $$$a$$$ 中至少出现 $$$k=2$$$ 次。

第一个条件成立且 $$$r-l$$$ 最大的一对 $$$l$$$ 和 $$$r$$$ 为 $$$l = 13$$$,$$$r = 14$$$。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \leq k \leq n$$$) — 数组 $$$a$$$ 的长度以及 $$$[l, r]$$$ 范围内每个数字应分别出现的最小次数。

接下来是一行,包含描述数组 $$$a$$$ 的 $$$n$$$ 整数 ($$$1 \leq a_i \leq 10^9$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出满足条件的 $$$2$$$ 数字、$$$l$$$ 和 $$$r$$$ ,如果没有数字满足条件,则输出“-1”。

如果存在多个答案,您可以输出任何答案。

示例

输入 #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