P14562 宇宙

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$ 时的答案。

### 样例 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$ | $80$ | 是 | | $3\sim5$ | $80$ | $80$ | 否 | | $6\sim8$ | $10^3$ | $10^9$ | 是 | | $9\sim12$ | $10^3$ | $10^9$ | 否 | | $13\sim14$ | $10^6$ | $10^6$ | 是 | | $15\sim16$ | $10^6$ | $10^6$ | 否 | | $17\sim18$ | $10^6$ | $10^9$ | 是 | | $19\sim20$ | $10^6$ | $10^9$ | 否 | 特殊性质：保证所有 $v_i$ 均相等。