Задача №115273. kex
Рассмотрим множество неотрицательных целых чисел \(A\). Минимальное неотрицательное целое число, которое не встречается в этом множестве, часто возникает, например, в теории игр, и обозначается как \(\mathrm{mex}(A)\). Например, \(\mathrm{mex}(\{0, 1, 2, 4, 5, 9\})=3\).
Аня решила обобщить понятие mex. Рассмотрим целое положительное число \(k\) и множество целых неотрицательных чисел \(A\). Обозначим как \(\mathrm{kex}(A, k)\) неотрицательное целое число, которое является \(k\)-м по возрастанию среди всех чисел, не входящих в \(A\). Например, \(\mathrm{kex}(\{0, 1, 2, 4, 5, 9\}, 2)=6\).
Требуется найти \(\mathrm{kex}(A, k_i)\) для заданного множества \(A\) и \(q\) значений \(k_i\).
В первой строке входных данных дано два числа \(n\) и \(q\) (\(1 \leqslant n, q \leqslant 10^5\)) — количество элементов во множестве \(A\) и количество значений \(\mathrm{kex}\), которое надо найти.
Во второй строке в порядке возрастания даны \(n\) различных чисел, не превышающих \(10^9\), — элементы множества \(A\).
В третьей строке даны \(q\) чисел \(k_i\) (\(1\leqslant k_i \leqslant 10^9\)).
Выведите \(q\) значений: \(\mathrm{kex}(A, k_1), \mathrm{kex}(A, k_2),\ldots, \mathrm{kex}(A, k_q)\).
4 10 1 2 6 7 1 2 3 4 5 6 7 8 10 11
0 3 4 5 8 9 10 11 13 14