No.2673 A present from B
Problem Statement
Next month, a gift exchange party will be held by $N$ people, including Alice and Bob. The gift exchange party will take place at Alice's house.
In Alice's house, $N$ chairs are arranged in a horizontal row, numbered $1, 2, \dots, N$ in order.
At the gift exchange party, Alice sits on chair $1$, and the other $N - 1$ participants each freely choose one of the chairs from $2$ to $N$ and sit on it.
At this point, all $N$ people sit holding the present they each brought.
Also, everyone has decided in advance on a sequence $A = (A_1, A_2, \dots, A_M)$ of length $M$.
The gift exchange party is carried out using this sequence $A$ as follows.
- Let $|A|$ be the length of the sequence $A$. For each $i = 1, 2, \dots, |A|$ in ascending order, repeat the following operation.
- The person sitting on chair $A_i$ and the person sitting on chair $A_i + 1$ exchange the presents they are holding.
After the above operations are finished, each person gets to keep the present they are holding.
Alice really wants to get Bob's present, so she has decided to cheat by rewriting the sequence $A$.
Alice can perform the following rewriting operation as many times as she likes.
- Let $|A|$ be the length of the current sequence $A$. Choose an integer $i \ (1 \leq i \leq |A| + 1)$ and an integer $X \ (1 \leq X \leq N - 1)$, and insert $X$ so that it becomes the $i$-th element from the front of $A$.
In other words, she can insert any integer between $1$ and $N-1$, inclusive, at any position in $A$ (including the front and the end).
On the day of the party, Alice sits on chair $1$ and waits for everyone. For each $i = 2, 3, \dots, N$, find the following value.
- The minimum number of rewriting operations required for Alice to finally get Bob's present when Bob sits on chair $i$ at the gift exchange party.
Input
The input is given from standard input in the following format.
$N$ $M$ $A_1$ $A_2$ $\dots$ $A_M$
Output
For each $2 \leq i \leq N$, let $B_i$ be the minimum number of rewriting operations required for Alice to get Bob's present when Bob sits on chair $i$.
Print $B_2, B_3, \dots, B_N$ in this order on one line to standard output, separated by spaces, followed by a newline.
Constraints
- All input values are integers.
- $2 \leq N \leq 500$
- $1 \leq M \leq 500$
- $1 \leq A_i \leq N - 1 \ (1 \leq i \leq M)$
Sample
Sample 1
Input
3 2 1 2
Output
0 1
Initially, $A = (1, 2)$.
If Bob sits on chair $2$, Alice, sitting on chair $1$, can get Bob's present without inserting any value into $A$.
If Bob sits on chair $3$, Alice can get Bob's present by, for example, inserting $2$ as the $1$-st element from the front of $A$ to make $A = (2, 1, 2)$.
Sample 2
Input
4 3 1 2 3
Output
0 1 2
The chairs are arranged in a horizontal row. Note that presents cannot be exchanged between the person sitting on chair $1$ and the person sitting on chair $4$.
Sample 3
Input
4 3 1 3 2
Output
0 1 1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
eoeo
Xelmeph
null
ngtkana