E - Organizing the Bookshelf Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君の本棚には N 冊の本が横一列に並べられています。最初、左から i 番目の位置にある本の耐久値は D_i です。

高橋君はこの本棚に対して Q 回の操作を順番に行います。j 回目の操作では、整数 T_j が与えられ、以下の手順で処理されます。

  1. そのとき本棚に残っている本の冊数を M とします。
  2. T_j > M の場合、左から T_j 番目の本は存在しないため、何も起こりません。
  3. T_j \leq M の場合、そのとき本棚の左から T_j 番目にある本の耐久値を 1 減らします。耐久値が 0 になった場合、その本は直ちに本棚から取り除かれます。取り除かれた本より右にあった本は、それぞれ 1 つずつ左の位置に移動し、残った本の間に隙間が生じないようになります。

各操作の後（何も起こらなかった場合も含む）に、本棚に残っている本の冊数を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq T_j \leq N (1 \leq j \leq Q)
  • 入力はすべて整数である。

注意: T_j は初期の冊数 N 以下ですが、操作時点での冊数 M を超える場合があります。その場合は上記の手順 2 により何も起こりません。

入力

N Q
D_1 D_2 \ldots D_N
T_1
T_2
\vdots
T_Q
  • 1 行目には、本の初期冊数を表す整数 N と、操作の回数を表す整数 Q が、スペース区切りで与えられる。
  • 2 行目には、左から i 番目の本の耐久値を表す整数 D_1, D_2, \ldots, D_N が、スペース区切りで与えられる。
  • 続く Q 行のうち j 行目 (1 \leq j \leq Q) には、j 回目の操作で対象となる位置を表す整数 T_j が与えられる。

出力

Q 行出力せよ。j 行目には、j 回目の操作の後に本棚に残っている本の冊数を出力せよ。

入力例 1

5 5
1 2 3 1 2
2
4
2
1
3

出力例 1

5
4
3
2
2

入力例 2

3 4
1 1 1
1
1
1
1

出力例 2

2
1
0
0

入力例 3

10 10
2 1 3 1 2 1 4 2 1 3
3
5
1
7
2
4
3
1
2
1

出力例 3

10
10
10
10
9
8
7
6
5
5

入力例 4

20 25
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4
1
3
5
7
2
10
15
1
3
5
8
12
1
1
2
4
6
3
2
1
5
4
3
2
1

出力例 4

20
20
20
20
19
19
19
19
18
17
17
17
16
16
16
16
16
16
16
16
16
16
16
16
15

入力例 5

1 1
1000000000
1

出力例 5

1

Score : 466 pts

Problem Statement

There are N books arranged in a horizontal row on Takahashi's bookshelf. Initially, the book at the i-th position from the left has a durability of D_i.

Takahashi performs Q operations on this bookshelf in order. In the j-th operation, an integer T_j is given, and the following procedure is carried out:

  1. Let M be the number of books currently remaining on the bookshelf.
  2. If T_j > M, the T_j-th book from the left does not exist, so nothing happens.
  3. If T_j \leq M, the durability of the book currently at the T_j-th position from the left on the bookshelf is decreased by 1. If the durability becomes 0, that book is immediately removed from the bookshelf. All books that were to the right of the removed book shift one position to the left, so that no gaps remain among the remaining books.

After each operation (including cases where nothing happens), output the number of books remaining on the bookshelf.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq T_j \leq N (1 \leq j \leq Q)
  • All input values are integers.

Note: T_j is at most the initial number of books N, but it may exceed the number of books M at the time of the operation. In that case, nothing happens as described in step 2 above.

Input

N Q
D_1 D_2 \ldots D_N
T_1
T_2
\vdots
T_Q
  • The first line contains two space-separated integers: N, the initial number of books, and Q, the number of operations.
  • The second line contains N space-separated integers D_1, D_2, \ldots, D_N, where D_i represents the durability of the i-th book from the left.
  • Each of the following Q lines contains a single integer T_j (1 \leq j \leq Q), representing the target position for the j-th operation.

Output

Output Q lines. The j-th line should contain the number of books remaining on the bookshelf after the j-th operation.

Sample Input 1

5 5
1 2 3 1 2
2
4
2
1
3

Sample Output 1

5
4
3
2
2

Sample Input 2

3 4
1 1 1
1
1
1
1

Sample Output 2

2
1
0
0

Sample Input 3

10 10
2 1 3 1 2 1 4 2 1 3
3
5
1
7
2
4
3
1
2
1

Sample Output 3

10
10
10
10
9
8
7
6
5
5

Sample Input 4

20 25
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4
1
3
5
7
2
10
15
1
3
5
8
12
1
1
2
4
6
3
2
1
5
4
3
2
1

Sample Output 4

20
20
20
20
19
19
19
19
18
17
17
17
16
16
16
16
16
16
16
16
16
16
16
16
15

Sample Input 5

1 1
1000000000
1

Sample Output 5

1