当前没有测试数据。

C - 邻近交换

得分：$300$ 分

问题描述

有 $N$ 个球从左到右排成一行。初始时，第 $i$ 个球（$1 \leq i \leq N$）上写有整数 $i$。

高桥进行了 $Q$ 次操作。第 $i$ 个（$1 \leq i \leq Q$）操作如下：

• 将上面写有整数 $x_i$ 的球与右边紧邻的球交换位置。如果写有整数 $x_i$ 的球本来就是最右边的球，则将其与左边紧邻的球交换位置。

设 $a_i$ 是操作后第 $i$ 个（$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$。

5 5
1
2
3
4
5

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$。

7 7
7
7
7
7
7
7
7

1 2 3 4 5 7 6

10 6
1
5
2
9
6
6

1 2 3 4 5 7 6 8 10 9