注意

こちらの問題の制約強化版です。

テスターのngtkanaさんによって考案されました。

問題文

来月に Alice さんと Bob さんを含む $N$ 人でプレゼント交換会を行うことになりました。 プレゼント交換会は Alice さんの家で行います。

Alice さんの家には $N$ 個の椅子が横一列に並んでおり、順に $1, 2, \dots, N$ の番号が付けられています。

プレゼント交換会では Alice さんが $1$ 番の椅子に座り、その他の $N - 1$ 人の参加者は $2$ 番から $N$ 番 までの椅子から自由にひとつずつ選んで座ります。

このとき、$N$ 人全員がそれぞれ持参したプレゼントを持って座ります。

また、全員で事前に長さ $M$ の数列 $A = (A_1, A_2, \dots, A_M)$ を決めました。

プレゼント交換会はこの数列 $A$ を用いて以下のように行います。

• 数列 $A$ の長さを $|A|$ とおく。各 $i = 1, 2, \dots, |A|$ に対して昇順に、次の操作を繰り返す。
  • $A_i$ 番の椅子に座っている人と $A_i + 1$ 番の椅子に座っている人とが持っているプレゼントを交換する。

以上の操作を終えた後に、各自が持っているプレゼントを獲得できます。

Alice さんは Bob さんのプレゼントをどうしても獲得したいと思い、数列 $A$ を書き換える不正をすることにしました。

Alice さんは次の書き換え操作を好きなだけ行うことができます。

• 現在の数列 $A$ の長さを $|A|$ とおく。整数 $i \ (1 \leq i \leq |A| + 1)$ と整数 $X \ (1 \leq X \leq N - 1)$ を選び、 $A$ の先頭から $i$ 番目に $X$ を挿入する。

すなわち、 $A$ の任意の位置（先頭と末尾を含む）へ $1$ 以上 $N-1$ 以下の任意の整数を挿入することが可能です。

当日 Alice さんは $1$ 番の椅子に座って皆を待ちます。 各 $i = 2, 3, \dots, N$ に対して、以下の値を求めてください。

• プレゼント交換会で Bob さんが $i$ 番の椅子に座ったとき、Alice さんが Bob さんのプレゼントを 最終的に 獲得するために必要な書き換え操作の最小回数。

入力

入力は以下の形式で標準入力から与えられます。

$N$ $M$
$A_1$ $A_2$ $\dots$ $A_M$

出力

各 $2 \leq i \leq N$ に対して、Bob さんが $i$ 番の椅子に座ったときに Alice さんが Bob さんのプレゼントを獲得するために必要な書き換え操作の最小回数を $B_i$ とします。

$B_2, B_3, \dots, B_N$ をこの順に空白区切りで標準出力へ一行で出力し、最後に改行してください。

制約

• 入力はすべて整数
• $2 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $1 \leq A_i \leq N - 1 \ (1 \leq i \leq M)$

サンプル

3 2
1 2

0 1

4 3
1 2 3

0 1 2

4 3
1 3 2

0 1 1