Adjacent Swaps

题目描述

$N$ 个球从左到右排成一行。最初，从左数第 $i$ 个（$1 \leq i \leq N$）球上写着整数 $i$。 Takahashi 进行了 $Q$ 次操作。第 $i$ 次（$1 \leq i \leq Q$）操作如下。

将写有整数 $x_i$ 的球与其右侧的相邻球交换。如果写有整数 $x_i$ 的球原本是最右边的球，则改为与左侧的相邻球交换。

令 $a_i$ 为操作结束后第 $i$ 个（$1 \leq i \leq N$）球上写的整数。求 $a_1,\ldots,a_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

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

提示

$2 \leq N \leq 2 \times 10^5$ $1 \leq Q \leq 2 \times 10^5$ $1 \leq x_i \leq N$ 输入中的所有数值都是整数。操作按如下方式进行。

将写有 $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$。

标签: AtCoder|abc250C

来源

AtCoder|abc250C