## LCC '18 Contest 5 S3 - Array Deletion

View as PDF

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Julian gave the following programming problem to his students : given an array of $$N$$ elements, remove the $$M$$ elements with indices $$K_1, K_2, ..., K_M$$.

A common solution that his students submitted looked as follows:

for (int i = 0; i < m; ++i) { // Iterate over array K.
A.remove(K.get(i)); // Remove K[i]th element from A.
}

Julian would like to show that this solution is incorrect. To do this, he would like to determine which elements are actually removed by this algorithm for a given input. Could you help him out?

#### Input Specification

The first line of input contains a two integers $$N, M$$ $$(1 \le N \le 10^9, 1 \le M \le 100,000)$$, the number of elements in the array and the number of elements to remove. The next line of input contains $$M$$ integers $$K_1, K_2, ..., K_M$$ $$(1 \le K_i \le N)$$, the indices to remove.

For 30 of 100 points, $$1 \le N, M \le 1000$$.
For 70 of 100 points, $$1 \le M \le 1000$$.

#### Output Specification

If at some point, the incorrect program would attempt an index that is out-of-bounds, output Out of bounds. Otherwise, print the set of original indices removed by the incorrect solution in sorted order.

#### Sample Input 1

5 2
2 4

#### Sample Output 1

2 5

#### Sample Input 2

5 3
1 1 4

#### Sample Output 2

Out of bounds