問題一覧 > 通常問題

No.2673 A present from B

レベル : / AI推定難易度 : 1425 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 88
作問者 : eoeo / テスター : Xelmeph nu50218 null ngtkana NokonoKotlin
お気に入りにしたユーザー ProblemId : 10652 / 自分の提出
問題文最終更新日: 2024-03-15 21:21:36
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 421 (NUPC2023) (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。