E - 図書館の本棚案内 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 433 点

問題文

高橋君は図書館でアルバイトをしています。この図書館には N 個の収納スペースが左から一列に並んだ本棚があり、各収納スペースには1冊の本を入れることができます。収納スペースには左から順に 1 番、 2 番、 \ldots 、 N 番と番号が振られています。最初、すべての収納スペースは空です。

今日は新しく届いた M 冊の本を本棚に並べる作業を担当しています。各本を配置すべき収納スペースの番号はあらかじめ決められており、配置順序が i 番目 (1 \leq i \leq M) である本は収納スペース S_i に配置します。どの2冊の本も異なる収納スペースに配置されます。すなわち S_1, S_2, \ldots, S_M はすべて異なる値です。高橋君は 1 冊目、 2 冊目、 \ldots 、 M 冊目の順に本を1冊ずつ本棚に配置していきます。

作業を効率化するため、高橋君は各本を配置する際に、その本を置くべき収納スペースが「その時点で空いている収納スペースの中で左から何番目にあたるか」を事前に知りたいと考えています。

具体的には、i 番目の本を配置する直前の時点で空いている収納スペースを左から順に 1, 2, \ldots と数えたとき、収納スペース S_i は左から P_i 番目にあたります。各 i = 1, 2, \ldots, M について P_i を求めてください。

制約

  • 1 \leq M \leq N \leq 2 \times 10^5
  • 1 \leq S_i \leq N
  • S_i はすべて異なる
  • 入力はすべて整数

入力

N M
S_1 S_2 \ldots S_M
  • 1 行目には、収納スペースの総数を表す整数 N と、配置する本の冊数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目には、各本を配置すべき収納スペースの番号 S_1, S_2, \ldots, S_M が、スペース区切りで与えられる。
  • S_i は配置順序が i 番目である本の収納スペース番号を表す。

出力

P_1
P_2
\vdots
P_M
  • M 行にわたって出力せよ。
  • i 行目には、 i 番目の本を配置する直前の時点で空いている収納スペースを左から順に数えたとき、収納スペース S_i が何番目であるかを表す整数 P_i を出力せよ。

入力例 1

5 3
3 1 5

出力例 1

3
1
3

入力例 2

10 6
2 7 4 1 10 5

出力例 2

2
6
3
1
6
2

入力例 3

20 10
15 3 18 7 1 20 10 5 12 8

出力例 3

15
3
16
6
1
15
7
3
7
4

Score : 433 pts

Problem Statement

Takahashi is working part-time at a library. The library has a bookshelf with N storage spaces arranged in a single row from left to right, and each storage space can hold one book. The storage spaces are numbered 1, 2, \ldots, N from left to right. Initially, all storage spaces are empty.

Today, Takahashi is in charge of placing M newly arrived books on the bookshelf. The storage space number where each book should be placed is predetermined: the book with placement order i (1 \leq i \leq M) is placed in storage space S_i. No two books are placed in the same storage space. That is, S_1, S_2, \ldots, S_M are all distinct values. Takahashi places the books one by one on the bookshelf in the order of the 1st book, the 2nd book, \ldots, the M-th book.

To make the task more efficient, Takahashi wants to know in advance, when placing each book, "among the storage spaces that are currently empty at that moment, what is the position from the left of the storage space where this book should be placed?"

Specifically, just before placing the i-th book, if we number the currently empty storage spaces 1, 2, \ldots from left to right, storage space S_i is the P_i-th from the left. Find P_i for each i = 1, 2, \ldots, M.

Constraints

  • 1 \leq M \leq N \leq 2 \times 10^5
  • 1 \leq S_i \leq N
  • All S_i are distinct
  • All input values are integers

Input

N M
S_1 S_2 \ldots S_M
  • The first line contains an integer N representing the total number of storage spaces and an integer M representing the number of books to be placed, separated by a space.
  • The second line contains the storage space numbers S_1, S_2, \ldots, S_M where each book should be placed, separated by spaces.
  • S_i represents the storage space number for the book with placement order i.

Output

P_1
P_2
\vdots
P_M
  • Output M lines.
  • On the i-th line, output an integer P_i representing the position of storage space S_i when counting the empty storage spaces from left to right just before placing the i-th book.

Sample Input 1

5 3
3 1 5

Sample Output 1

3
1
3

Sample Input 2

10 6
2 7 4 1 10 5

Sample Output 2

2
6
3
1
6
2

Sample Input 3

20 10
15 3 18 7 1 20 10 5 12 8

Sample Output 3

15
3
16
6
1
15
7
3
7
4