题目描述

Yuki 是一个来自异世界的次元少女！

她生活在 $n$ 维宇宙的一艘飞船上，坐标为 $(v_1,\dots,v_n)$。突然，她的探测器显示宇宙原点处有一个黑洞正在扩张：对于所有正整数 $i$，在第 $i$ 秒时，如果飞船的某一维坐标小于或等于 $i$，那么 Yuki 和她的飞船就会被黑洞吃掉！

为了逃生，Yuki 需要尽力远离黑洞：对于所有正整数 $i$，在第 $i-0.5$ 秒时，如果 Yuki 还没有被黑洞吃掉，那么她需要选择 $k$ 个不同的维度 $s_1,\dots,s_k$，将 $v_{s_1},\dots,v_{s_k}$ 均增加 $1$。

不过，由于飞船的仪表盘坏了，Yuki 并不知道飞船还剩余多少燃料。所以，她想请你对于每个小于 $n$ 的正整数 $k$ 求出最大的非负整数 $x$，满足在最优策略下，第 $x$ 秒时 Yuki 还没有被黑洞吃掉。容易证明这样的非负整数 $x$ 存在。

输入格式

第一行包含两个整数 $c,n$，其中 $c$ 表示测试点编号。$c=0$ 表示该测试点为样例。

第二行包含 $n$ 个整数 $v_1,\dots,v_n$。

输出格式

输出一行，包含 $n-1$ 个整数，其中第 $i$ 个整数表示 $k=i$ 时的答案。

0 3
1 2 3

1 3

提示

样例 1 解释

对于 $k=1$ 的情况，Yuki 可以在第 $0.5$ 秒时将坐标从 $(1,2,3)$ 修改为 $(2,2,3)$。容易证明在第 $2$ 秒时 Yuki 一定会被黑洞吃掉，所以答案为 $1$。

对于 $k=2$ 的情况，Yuki 可以在第 $0.5,1.5,2.5$ 秒时将坐标分别修改为 $(2,3,3),(3,3,4),(4,4,4)$。容易证明在第 $4$ 秒时 Yuki 一定会被黑洞吃掉，所以答案为 $3$。

样例 2

见下发文件中的 $\textbf{\textit{universe/universe2.in}}$ 与 $\textbf{\textit{universe2.ans}}$。

该组样例满足测试点 $3$ 的限制。

样例 3

见下发文件中的 $\textbf{\textit{universe/universe3.in}}$ 与 $\textbf{\textit{universe3.ans}}$。

该组样例满足测试点 $6$ 的限制。

样例 4

见下发文件中的 $\textbf{\textit{universe/universe4.in}}$ 与 $\textbf{\textit{universe4.ans}}$。

该组样例满足测试点 $9$ 的限制。

样例 5

见下发文件中的 $\textbf{\textit{universe/universe5.in}}$ 与 $\textbf{\textit{universe5.ans}}$。

该组样例满足测试点 $15$ 的限制。

样例 6

见下发文件中的 $\textbf{\textit{universe/universe6.in}}$ 与 $\textbf{\textit{universe6.ans}}$。

该组样例满足测试点 $20$ 的限制。

数据范围

对于所有测试数据，保证：

• $2 \le n \le 10^6$；
• $1 \le v_i \le 10^9$。

::cute-table{tuack}

测试点编号	$n \le$	$v_i \le$	特殊性质
$1\sim2$	$80$		是
$3\sim5$			否
$6\sim8$	$10^3$	$10^9$	是
$9\sim12$			否
$13\sim14$	$10^6$	$10^6$	是
$15\sim16$			否
$17\sim18$		$10^9$	是
$19\sim20$			否

特殊性质：保证所有 $v_i$ 均相等。