E - Cheating Amidakuji Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

1 以上 N-1 以下の整数からなる長さ M の数列 A=(A_1,A_2,\dots,A_M) が与えられます。 i=1,2,\dots,M について、以下の質問に答えてください。

  • 数列 B=(B_1,B_2,\dots,B_N) がある。最初、各 j について B_j=j である。今から、k=1,2,\dots,i-1,i+1,\dots,M の順に以下の操作を行う （すなわち、i を除いた 1 以上 M 以下の整数 k について、昇順に以下の操作を行う）。
    • B_{A_k} と B_{A_k+1} の値を入れ替える。
  • 全ての操作が終了した段階で、B_j=1 を満たす j の値を S_i と定義する。S_i を求めよ。

制約

  • 2 \leq N \leq 2\times 10^5
  • 1 \leq M \leq 2\times 10^5
  • 1 \leq A_i \leq N-1\ (1\leq i \leq M)
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 A_2 \dots A_M

出力

M 行出力せよ。 i\ (1\leq i \leq M) 行目には、S_i の値を整数として出力せよ。

入力例 1

5 4
1 2 3 2

出力例 1

1
3
2
4

i = 2 のとき、操作によって B は以下のように変化します。

  • 最初、B = (1,2,3,4,5)
  • k=1 として操作を行う。すなわち B_1 と B_2 の値を入れ替えて、B = (2,1,3,4,5)
  • k=3 として操作を行う。すなわち B_3 と B_4 の値を入れ替えて、B = (2,1,4,3,5)
  • k=4 として操作を行う。すなわち B_2 と B_3 の値を入れ替えて、B = (2,4,1,3,5)

全ての操作が終了した段階で B_3=1 であるため、S_2 = 3 です。

同様に、

  • i=1 のとき：k=2,3,4 の順に操作を行うと B=(1,4,3,2,5) になるので、S_1=1
  • i=3 のとき：k=1,2,4 の順に操作を行うと B=(2,1,3,4,5) になるので、S_3=2
  • i=4 のとき：k=1,2,3 の順に操作を行うと B=(2,3,4,1,5) になるので、S_4=4

です。

入力例 2

3 3
2 2 2

出力例 2

1
1
1

入力例 3

10 10
1 1 1 9 4 4 2 1 3 3

出力例 3

2
2
2
3
3
3
1
3
4
4

Score : 500 points

Problem Statement

You are given a sequence of length M consisting of integers between 1 and N-1, inclusive: A=(A_1,A_2,\dots,A_M). Answer the following question for i=1, 2, \dots, M.

  • There is a sequence B=(B_1,B_2,\dots,B_N). Initially, we have B_j=j for each j. Let us perform the following operation for k=1, 2, \dots, i-1, i+1, \dots, M in this order (in other words, for integers k between 1 and M except i in ascending order).
    • Swap the values of B_{A_k} and B_{A_k+1}.
  • After all the operations, let S_i be the value of j such that B_j=1. Find S_i.

Constraints

  • 2 \leq N \leq 2\times 10^5
  • 1 \leq M \leq 2\times 10^5
  • 1 \leq A_i \leq N-1\ (1\leq i \leq M)
  • 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 \dots A_M

Output

Print M lines. The i-th line (1\leq i \leq M) should contain the value S_i as an integer.

Sample Input 1

5 4
1 2 3 2

Sample Output 1

1
3
2
4

For i = 2, the operations change B as follows.

  • Initially, B = (1,2,3,4,5).
  • Perform the operation for k=1. That is, swap the values of B_1 and B_2, making B = (2,1,3,4,5).
  • Perform the operation for k=3. That is, swap the values of B_3 and B_4, making B = (2,1,4,3,5).
  • Perform the operation for k=4. That is, swap the values of B_2 and B_3, making B = (2,4,1,3,5).

After all the operations, we have B_3=1, so S_2 = 3.

Similarly, we have the following.

  • For i=1: performing the operation for k=2,3,4 in this order makes B=(1,4,3,2,5), so S_1=1.
  • For i=3: performing the operation for k=1,2,4 in this order makes B=(2,1,3,4,5), so S_3=2.
  • For i=4: performing the operation for k=1,2,3 in this order makes B=(2,3,4,1,5), so S_4=4.

Sample Input 2

3 3
2 2 2

Sample Output 2

1
1
1

Sample Input 3

10 10
1 1 1 9 4 4 2 1 3 3

Sample Output 3

2
2
2
3
3
3
1
3
4
4