Tanya and Toys
Contest: Codeforces Round 346 (Div. 2)
Difficulty rating: 1200
Tags: greedy, implementation

In Berland recently a new collection of toys went on sale. This collection consists of 109 types of toys, numbered with integers from 1 to 109. A toy from the new collection of the i-th type costs i bourles.

Tania has managed to collect n different types of toys a1, a2, ..., an from the new collection. Today is Tanya's birthday, and her mother decided to spend no more than m bourles on the gift to the daughter. Tanya will choose several different types of toys from the new collection as a gift. Of course, she does not want to get a type of toy which she already has.

Tanya wants to have as many distinct types of toys in her collection as possible as the result. The new collection is too diverse, and Tanya is too little, so she asks you to help her in this.

Input format:
The first line contains two integers n (1 ≤ n ≤ 100 000) and m (1 ≤ m ≤ 109) — the number of types of toys that Tanya already has and the number of bourles that her mom is willing to spend on buying new toys.

The next line contains n distinct integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the types of toys that Tanya already has.

Output format:
In the first line print a single integer k — the number of different types of toys that Tanya should choose so that the number of different types of toys in her collection is maximum possible. Of course, the total cost of the selected toys should not exceed m.

In the second line print k distinct space-separated integers t1, t2, ..., tk (1 ≤ ti ≤ 109) — the types of toys that Tanya should choose.

If there are multiple answers, you may print any of them. Values of ti can be printed in any order.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first sample mom should buy two toys: one toy of the 2-nd type and one toy of the 5-th type. At any other purchase for 7 bourles (assuming that the toys of types 1, 3 and 4 have already been bought), it is impossible to buy two and more toys.

Example input:
3 7
1 3 4

Example output:
2
2 5

Example input:
4 14
4 6 12 8

Example output:
4
7 2 3 1

Editorial:
Our task is to take largest amount of toys Tanya doesn't have yet the way the sum of their costs doesn't exceed m. To do that one can perform greedy algorithm: let's buy the cheepest toy Tanya doesn't have at every step, while the amount of money left are sufficient to do that. The boolean array used can be a handle in that, storing true values in indices equal to toy types which Tanya does have at the moment. As soon as 109 money is sufficient to buy no more than 105 toys $$( \frac { 1 0 ^ { 5 } \times ( 1 0 ^ { 5 } + 1 ) } { 2 } \geq 1 0 ^ { 9 } )$$, used is enough to be sized 2 × 105 (we won't buy the toys with types numbered greater). So we just need to iterate over the number of type we want to buy, and if corresponding value in used is equal to false, we should buy it, otherwise we can't.
The solution complexity is $$O(n + \sqrt{m})$$.
One can use the «set» data structure (C++ std::set, for example), for storing the types Tanya has at the moment. In this case the complexity is $${ \mathcal { O } } ( n + { \sqrt { m } } \log n )$$.