题目描述
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 输入
0 3 1 2 3
样例 1 输出
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
见下发文件中的 $\textit{universe/universe2.in}$ 与 $\textit{universe2.ans}$。
该组样例满足测试点 $3$ 的限制。
样例 3
见下发文件中的 $\textit{universe/universe3.in}$ 与 $\textit{universe3.ans}$。
该组样例满足测试点 $6$ 的限制。
样例 4
见下发文件中的 $\textit{universe/universe4.in}$ 与 $\textit{universe4.ans}$。
该组样例满足测试点 $9$ 的限制。
样例 5
见下发文件中的 $\textit{universe/universe5.in}$ 与 $\textit{universe5.ans}$。
该组样例满足测试点 $15$ 的限制。
样例 6
见下发文件中的 $\textit{universe/universe6.in}$ 与 $\textit{universe6.ans}$。
该组样例满足测试点 $20$ 的限制。
数据范围
对于所有测试数据，保证：
- $2 \le n \le 10^6$；
- $1 \le v_i \le 10^9$。
| 测试点编号 | $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$ 均相等。