题目描述
$ 1 $ 以上 $ N-1 $ 以下の整数からなる長さ $ M $ の数列 $ A=(A_1,A_2,\dots,A_M) $ が与えられます。 $ i=1,2,\dots,M $ について、以下の質問に答えてください。
- 数列 B=(B1,B2,…,BN) がある。最初、各 j について Bj=j である。今から、k=1,2,…,i−1,i+1,…,M の順に以下の操作を行う (すなわち、i を除いた 1 以上 M 以下の整数 k について、昇順に以下の操作を行う)。
- BAk と BAk+1 の値を入れ替える。
- 全ての操作が終了した段階で、Bj=1 を満たす j の値を Si と定義する。Si を求めよ。
输入格式
入力は以下の形式で標準入力から与えられる。
N M A1 A2 … AM
输出格式
M 行出力せよ。 i (1≤ i ≤ M) 行目には、Si の値を整数として出力せよ。
题目大意
给你两个数组 A 和 B,初始时,Bi=i。
定义第 k 次操作为 swap(BAk,BAk+1)
定义 Si 为依次进行 1 到 m 除 i 号操作外的所有操作后,数字 1 在 B 数组中的位置。
请依次输出 Si 。
5 4
1 2 3 2
1
3
2
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
提示
制約
- 2 ≤ N ≤ 2× 105
- 1 ≤ M ≤ 2× 105
- 1 ≤ Ai ≤ N−1 (1≤ i ≤ M)
- 入力は全て整数
Sample Explanation 1
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 です。