配点 : 500 点
問題文
1 以上 N−1 以下の整数からなる長さ M の数列 A=(A1,A2,…,AM) が与えられます。
i=1,2,…,M について、以下の質問に答えてください。
- 数列 B=(B1,B2,…,BN) がある。最初、各 j について Bj=j である。今から、k=1,2,…,i−1,i+1,…,M の順に以下の操作を行う
(すなわち、i を除いた 1 以上 M 以下の整数 k について、昇順に以下の操作を行う)。- BAk と BAk+1 の値を入れ替える。
- BAk と BAk+1 の値を入れ替える。
- 全ての操作が終了した段階で、Bj=1 を満たす j の値を Si と定義する。Si を求めよ。
制約
- 2≤N≤2×105
- 1≤M≤2×105
- 1≤Ai≤N−1 (1≤i≤M)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M
A1 A2 … AM
出力
M 行出力せよ。
i (1≤i≤M) 行目には、Si の値を整数として出力せよ。
5 4
1 2 3 2
1
3
2
4
i=2 のとき、操作によって B は以下のように変化します。
- 最初、B=(1,2,3,4,5)
- k=1 として操作を行う。すなわち B1 と B2 の値を入れ替えて、B=(2,1,3,4,5)
- k=3 として操作を行う。すなわち B3 と B4 の値を入れ替えて、B=(2,1,4,3,5)
- k=4 として操作を行う。すなわち B2 と B3 の値を入れ替えて、B=(2,4,1,3,5)
全ての操作が終了した段階で B3=1 であるため、S2=3 です。
同様に、
- i=1 のとき:k=2,3,4 の順に操作を行うと B=(1,4,3,2,5) になるので、S1=1
- i=3 のとき:k=1,2,4 の順に操作を行うと B=(2,1,3,4,5) になるので、S3=2
- i=4 のとき:k=1,2,3 の順に操作を行うと B=(2,3,4,1,5) になるので、S4=4
です。
3 3
2 2 2
1
1
1
10 10
1 1 1 9 4 4 2 1 3 3
2
2
2
3
3
3
1
3
4
4