102724: [AtCoder]ABC272 E - Add and Mex

Problem Statement

You are given an integer sequence $A=(A_1,A_2,\ldots,A_N)$ of length $N$.

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$.

Constraints

• $1\leq N,M \leq 2\times 10^5$
• $-10^9\leq A_i\leq 10^9$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$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.

Sample Input 1

3 3
-1 -1 -6

Sample Output 1

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 Input 2

5 6
-2 -2 -5 -7 -15

Sample Output 2

1
3
2
0
0
0

问题描述

你被给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$。

执行以下 $M$ 次操作：

• 对于每个 $i\ (1\leq i \leq N)$，将 $i$ 添加到 $A_i$。 然后，找到不包含在 $A$ 中的最小非负整数。

约束条件

• $1\leq N,M \leq 2\times 10^5$
• $-10^9\leq A_i\leq 10^9$
• 输入中的所有值都是整数。

输入

输入从标准输入以以下格式给出：

$N$ $M$ 
$A_1$ $A_2$ $\ldots$ $A_N$

输出

打印 $M$ 行。

第 $i$ 行 $(1\leq i \leq M)$ 应包含第 $i$ 次操作后不包含在 $A$ 中的最小非负整数。

样例输入 1

3 3
-1 -1 -6

样例输出 1

2
2
0

第 $1$ 次操作使序列 $A$ 变为

$(-1 + 1, -1 +2 ,-6+3) = (0,1,-3).$

不包含在 $A$ 中的最小非负整数是 $2$。

第 $2$ 次操作使序列 $A$ 变为

$(0 + 1, 1 +2 ,-3+3) = (1,3,0).$

不包含在 $A$ 中的最小非负整数是 $2$。

第 $3$ 次操作使序列 $A$ 变为

$(1 + 1, 3 +2 ,0+3) = (2,5,3).$

不包含在 $A$ 中的最小非负整数是 $0$。

样例输入 2

5 6
-2 -2 -5 -7 -15

样例输出 2

1
3
2
0
0
0