← 返回题目列表

Codeforces · 1330/A

A. Dreamoon 和排名合集

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

Dreamoon 是 Codeforces 竞赛的忠实粉丝。

有一天,他声称在再进行两场评级比赛后,他将收集从 $$$1$$$ 到 $$$54$$$ 的所有名额。太棒了!

基于此,您提出以下问题:

有人参加了 $$$n$$$ Codeforces 轮次。他在第一轮的位置是$$$a_1$$$,他在第二轮的位置是$$$a_2$$$,...,他在第$$$n$$$轮的位置是$$$a_n$$$。

给你一个非零正整数$$$x$$$。

请找到最大的 $$$v$$$,以便此人可以在 $$$x$$$ 更多评级比赛后收集从 $$$1$$$ 到 $$$v$$$ 的所有名次。

换句话说,你需要找到最大的 $$$v$$$,这样就有可能在 $$$x$$$ 次评级比赛之后,对于每个 $$$1 \leq i \leq v$$$,将存在一个比赛,其中此人获得第 $$$i$$$ 名。

例如,如果 $$$n=6$$$、$$$x=2$$$ 和 $$$a=[3,1,1,5,7,10]$$$,那么答案是 $$$v=5$$$,因为如果在接下来的两场比赛中他将获得 $$$2$$$ 和 $$$4$$$ 的位置,那么他将收集从 $$$1$$$ 到 $$$1$$$ 的所有位置$$$5$$$,因此可以得到$$$v=5$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 5$$$) 表示输入中测试用例的数量。

每个测试用例包含两行。第一行包含两个整数 $$$n, x$$$ ($$$1 \leq n, x \leq 100$$$)。第二行包含 $$$n$$$ 正非零整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 100$$$)。

输出

对于每个测试用例,打印一行包含最大的 $$$v$$$,这样有可能在 $$$x$$$ 其他竞赛之后,对于每个 $$$1 \leq i \leq v$$$,将存在一个竞赛,其中此人获得第 $$$i$$$ 位。

示例

输入 #1

5
6 2
3 1 1 5 7 10
1 100
100
11 1
1 1 1 1 1 1 1 1 1 1 1
1 1
1
4 57
80 60 40 20

输出 #1

5
101
2
2
60

注意

声明中描述了第一个测试用例。

在第二个测试用例中,该人有一百场未来的比赛,因此他可以参加 $$$1,2,\ldots,99$$$ 并按某种顺序将 $$$101$$$ 放在上面,以收集位置 $$$1,2,\ldots,101$$$。