102502: [AtCoder]ABC250 C - Adjacent Swaps

Problem Statement

$N$ balls are lined up in a row from left to right. Initially, the $i$-th ($1 \leq i \leq N$) ball from the left has an integer $i$ written on it.

Takahashi has performed $Q$ operations. The $i$-th ($1 \leq i \leq Q$) operation was as follows.

• Swap the ball with the integer $x_i$ written on it with the next ball to the right. If the ball with the integer $x_i$ written on it was originally the rightmost ball, swap it with the next ball to the left instead.

Let $a_i$ be the integer written on the $i$-th ($1 \leq i \leq N$) ball after the operations. Find $a_1,\ldots,a_N$.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq x_i \leq N$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $Q$
$x_1$
$\vdots$
$x_Q$

Output

Print $a_1,\ldots,a_N$, with spaces in between.

Sample Input 1

5 5
1
2
3
4
5

Sample Output 1

1 2 3 5 4

The operations are performed as follows.

• Swap the ball with $1$ written on it with the next ball to the right. Now, the balls have integers $2,1,3,4,5$ written on them, from left to right.
• Swap the ball with $2$ written on it with the next ball to the right. Now, the balls have integers $1,2,3,4,5$ written on them, from left to right.
• Swap the ball with $3$ written on it with the next ball to the right. Now, the balls have integers $1,2,4,3,5$ written on them, from left to right.
• Swap the ball with $4$ written on it with the next ball to the right. Now, the balls have integers $1,2,3,4,5$ written on them, from left to right.
• Swap the ball with $5$ written on it with the next ball to the left, since it is the rightmost ball. Now, the balls have integers $1,2,3,5,4$ written on them, from left to right.

Sample Input 2

7 7
7
7
7
7
7
7
7

Sample Output 2

1 2 3 4 5 7 6

Sample Input 3

10 6
1
5
2
9
6
6

Sample Output 3

1 2 3 4 5 7 6 8 10 9

问题描述

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

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

• 将写有整数$x_i$的球与其右边的下一个球交换。如果原本写有整数$x_i$的球是最右边的球，则将其与左边的下一个球交换。

设操作结束后，第$i$个球（$1 \leq i \leq N$）上写的整数为$a_i$。请找出$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