Dreamoon — большой фанат соревнований на Codeforces!
Однажды, он сказал, что соберет все места от $$$1$$$ до $$$54$$$ после двух следующих рейтинговых контестов. Это удивительно!
Вдохновившись его высказыванием, вы придумали следующую задачу:
Есть человек, который принял участие в $$$n$$$ раундах на Codeforces. Его место на первом раунде — $$$a_1$$$, его место на втором раунде — $$$a_2$$$, ..., его место на $$$n$$$-м раунде — $$$a_n$$$.
Вам дано положительное целое число $$$x$$$.
Пожалуйста, найдите наибольшее такое $$$v$$$, что этот человек сможет собрать все места от $$$1$$$ до $$$v$$$ спустя $$$x$$$ следующих рейтинговых контестов.
Другими словами, вам нужно найти наибольшее $$$v$$$, что возможно такое, что после $$$x$$$ следующих контестов, для каждого $$$1 \leq i \leq v$$$, будет существовать контест, в котором он занял $$$i$$$-е место.
Например, если $$$n=6$$$, $$$x=2$$$ и $$$a=[3,1,1,5,7,10]$$$, то ответ $$$v=5$$$, так как, если занятые места в двух следующих раундах будут $$$2$$$ и $$$4$$$, то будут собраны все места от $$$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$$$-е место.
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
5 101 2 2 60
Первый набор входных данных разобран в условии.
Во втором наборе входных данных, у человека есть сто будущих контестов, так что он может занять места $$$1,2,\ldots,99$$$ и место $$$101$$$ на них в каком-то порядке, чтобы собрать места $$$1,2,\ldots,101$$$.
Название |
---|