Задача №113945. Индра и mex
Индра — большой любитель математики. Читая книгу по теории игр, он наткнулся на интересную функцию \(mex\). Она определяется следующим образом: \(mex(A)\) — это минимальное положительное целое число, которое отсутствует в множестве \(A\). Например, \(mex\) множества \(\{1, 2, 3, 5, 100\}\) равен \(4\), а \(mex\) множества \(\{2, 3, 4, 5\}\) равен \(1\).
Чтобы поупражняться с применением функции \(mex\), Индра взял множество чисел \(A\), состоящее из \(n\) целых положительных чисел, и положительное число \(k\). Затем Индра \(k\) раз произвёл следующую операцию: он добавил в множество \(A\) ещё одно число, равное \(mex(A)\), тем самым, каждый раз увеличивая размер множества \(A\) на один.
По заданному множеству \(A\) и числу \(k\) определите последнее число, которое Индра добавит в множество.
В первой строке заданы два целых числа \(n\) и \(k\) (\(1 \leq n \leq 100\,000\), \(1 \leq k \leq 10^9\)) — количество чисел в множестве и количество операций добавления числа, произведённых Индрой.
Вторая строка содержит \(n\) различных целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq 100\,000\)) — элементы множества \(A\).
Выведите одно целое число — последнее число, которое Индра добавит в множество.
В первом примере \(mex\) множества \(\{1, 2, 4, 5\}\) равен \(3\), после добавления \(mex\) в множество, оно станет равным \(\{1, 2, 3, 4, 5\}\).
4 1 4 2 1 5
3
7 10 1 3 20 2 7 45 5
15