Score : $300$ points

问题描述

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

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 10:41:03