/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
以下の操作を M 回行ってください。
- 各 i\ (1\leq i \leq N) について、 A_i に 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
Score : 500 points
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