分数: 300 点
问题陈述
N 球从左到右排成一排。 最初, i-th (1 \leq i \leq N) 左边的球有一个整数 i 。
高桥已表演 Q 操作。 的 i-th (1 \leq i \leq Q)操作如下。
- 将球与整数交换 上面写着 x_i ,下一个球在右边。 如果球带有整数 上面写的 x_i 原本是最右边的球,与左边的下一个球交换。
让 a_i 是写在 i-th (1 \leq i \leq N) 操作后的球。 查找 a_1,\ldots,a_N.
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq x_i \leq N
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N Q x_1 \vdots x_Q
输出
打印 a_1,\ldots,a_N,之间有空格。
示例输入 1
5 5 1 2 3 4 5
示例输出 1
1 2 3 5 4
操作执行如下。
- 将球与 上面写着 1 ,下一个球在右边。 现在,球有整数 上面从左到右写着 2,1,3,4,5 。
- 将球与 上面写着 2 ,下一个球在右边。 现在,球有整数 上面从左到右写着 1,2,3,4,5 。
- 将球与 上面写着 3 ,下一个球在右边。 现在,球有整数 上面从左到右写着 1,2,4,3,5 。
- 将球与 上面写着 4 ,下一个球在右边。 现在,球有整数 上面从左到右写着 1,2,3,4,5 。
- 将球与 上面写着 5 ,下一个球在左边,因为它是最右边的球。 现在,球有整数 1,2,3,5,4 。
示例输入 2
7 7 7 7 7 7 7 7 7
示例输出 2
1 2 3 4 5 7 6
示例输入 3
10 6 1 5 2 9 6 6
示例输出 3
1 2 3 4 5 7 6 8 10 9