No.2690 A present from B (Hard)
Note
This is a version of this problem with stricter constraints.
It was devised by the tester, ngtkana.
Problem Statement
Next month, $N$ people including Alice and Bob will hold a present exchange party. The present exchange party will be held 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 present exchange party, Alice sits on chair $1$, and the other $N - 1$ participants freely choose one chair each from chairs $2$ through $N$ and sit on them.
At this time, all $N$ people sit holding the present that each of them brought.
In addition, everyone has decided in advance on a sequence $A = (A_1, A_2, \dots, A_M)$ of length $M$.
The present 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 desperately wants to get Bob's present, so she has decided to cheat by rewriting the sequence $A$.
Alice can perform the following rewriting operation any number of times.
- 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$ at the $i$-th position from the front of $A$.
In other words, she can insert any integer between $1$ and $N-1$, inclusive, at any position of $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 present 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 inputs are integers.
- $2 \leq N \leq 10^5$
- $1 \leq M \leq 10^5$
- $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$ at the $1$-st position 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 the person sitting on chair $1$ and the person sitting on chair $4$ cannot exchange presents with each other.
Sample 3
Input
4 3 1 3 2
Output
0 1 1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
eoeo
ngtkana