Codeforces Round 346 (Div. 2) |
---|
Закончено |
В Берляндии недавно появилась в продаже новая коллекция игрушек. В этой коллекции 109 типов игрушек, пронумерованных целыми числами от 1 до 109. Игрушка из новой коллекции i-го типа стоит i бурлей.
Таня уже успела собрать n игрушек различных типов a1, a2, ..., an из новой коллекции. Сегодня у Тани день рождения, и её мама решила потратить не более m бурлей на подарок дочери. Таня в качестве подарка выберет несколько игрушек различных типов из новой коллекции. Конечно, она не хочет получить в качестве подарка игрушку того типа, которая у неё уже есть.
Таня хочет, чтобы в результате в её коллекции было как можно больше различных типов игрушек. Новая коллекция слишком разнообразна, а Таня еще слишком мала, поэтому она просит вас помочь ей в этом.
В первой строке содержатся два целых числа n (1 ≤ n ≤ 100 000) и m (1 ≤ m ≤ 109) — количество типов игрушек, которые уже есть у Тани, и количество бурлей, которые мама готова потратить на покупку новых игрушек.
В следующей строке содержатся n различных целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109) — типы игрушек, которые у Тани уже есть.
В первой строке выведите единственное целое число k — количество игрушек различных типов, которые следует выбрать Тане, чтобы количество различных типов игрушек в её коллекции стало максимально возможным. Разумеется, суммарная стоимость выбранных игрушек не должна превышать m.
Во второй строке выведите k разделённых пробелами различных целых чисел t1, t2, ..., tk (1 ≤ ti ≤ 109) — типы игрушек, которые следует выбрать Тане.
Если ответов несколько, разрешается вывести любой из них. Значения ti можно выводить в любом порядке.
3 7
1 3 4
2
2 5
4 14
4 6 12 8
4
7 2 3 1
В первом примере мама должна купить две игрушки: одну игрушку 2-го типа и одну игрушку 5-го типа. При любой другой покупке на 7 бурлей (учитывая, что игрушки типов 1, 3 и 4 уже куплены), купить две и более игрушек не получится.
Название |
---|