7174: ABC272 —— E - Add and Mex
[Creator : ]
Description
You are given an integer sequence $A=(A_1,A_2,\ldots,A_N)$ of length $N$.
Perform the following operation $M$ times:
Perform the following operation $M$ times:
- For each $i\ (1\leq i \leq N)$, add i to $A_i$. Then, find the minimum non-negative integer not contained in $A$.
Input
The input is given from Standard Input in the following format:
$N\ M$
$A_1\ A_2\ \ldots\ A_N$
$N\ M$
$A_1\ A_2\ \ldots\ A_N$
Output
Print $M$ lines.
The i-th ($1\leq i \leq M$) line should contain the minimum non-negative integer not contained in A after the i-th operation.
The i-th ($1\leq i \leq M$) line should contain the minimum non-negative integer not contained in A after the i-th operation.
Constraints
$1≤N,M≤2×10^5$
$-10^9\leq A_i\leq 10^9$
All values in the input are integers.
$-10^9\leq A_i\leq 10^9$
All values in the input are integers.
Sample 1 Input
3 3
-1 -1 -6
Sample 1 Output
2
2
0
The 1-st operation makes the sequence A
(-1 + 1, -1 +2 ,-6+3) = (0,1,-3).
The minimum non-negative integer not contained in A is 2.
The 2-nd operation makes the sequence A
(0 + 1, 1 +2 ,-3+3) = (1,3,0).
The minimum non-negative integer not contained in A is 2.
The 3-rd operation makes the sequence A
(1 + 1, 3 +2 ,0+3) = (2,5,3).
The minimum non-negative integer not contained in A is 0.
Sample 2 Input
5 6
-2 -2 -5 -7 -15
Sample 2 Output
1
3
2
0
0
0